Юнит на последнем месте

В информатике и анализе численном единица на последнем месте или единица наименьшей точности ( ulp ) — это расстояние между двумя последовательными числами с плавающей запятой , т. е. значение, которое представляет младшая значащая цифра (крайняя правая цифра), если она равна 1. используется как мера точности в числовых вычислениях. ^[1]

Определение

Наиболее распространенное определение: В системе счисления. $b$ с точностью $p$ , если $b^{e}\leq |x|<b^{e+1}$ , затем $\operatorname {ulp} (x)=b^{\max\{e,\,e_{\min }\}-p+1}$ , ^[2] где $e_{\min }$ — минимальный показатель нормальных чисел. В частности, $\operatorname {ulp} (x)=b^{e-p+1}$ для нормальных чисел и $\operatorname {ulp} (x)=b^{e_{\min }-p+1}$ были субнормальными .

Другое определение, предложенное Джоном Харрисоном, немного отличается: $\operatorname {ulp} (x)$ расстояние между двумя ближайшими числами с плавающей запятой $a$ и $b$ (т.е. удовлетворение $a\leq x\leq b$ и $a\neq b$ ), предполагая, что диапазон показателей не ограничен сверху. ^[3]^[4] Эти определения различаются только знаковыми степенями основания. ^[2]

Спецификация IEEE 754 , которой следует все современное оборудование с плавающей запятой, требует, чтобы результат элементарной арифметической операции (сложение, вычитание, умножение, деление и извлечение квадратного корня с 1985 года и FMA с 2008 года) был правильно округлен , что означает, что при округлении до ближайшего значения округленный результат находится в пределах 0,5 ulp от математически точного результата, используя определение Джона Харрисона; и наоборот, это свойство означает, что расстояние между округленным результатом и математически точным результатом сведено к минимуму (но для промежуточных случаев оно удовлетворяется двумя последовательными числами с плавающей запятой). Авторитетные числовые библиотеки вычисляют основные трансцендентные функции с точностью от 0,5 до примерно 1 ulp. Лишь немногие библиотеки вычисляют их с точностью до 0,5 ulp, причем эта проблема сложна из-за дилеммы Создателя Таблиц . ^[5]

С 2010-х годов достижения в области математики с плавающей запятой позволили правильно округленным функциям работать в среднем почти так же быстро, как и эти более ранние, менее точные функции. Правильно округленная функция также будет полностью воспроизводимой. Более ранней промежуточной вехой стали функции ulp 0,501. ^{[ нужны разъяснения ]} что теоретически приведет только к одному неправильному округлению из 1000 случайных входных данных с плавающей запятой. ^[6]

Примеры

Пример 1

Позволять $x$ быть положительным числом с плавающей запятой и предположим, что активный режим округления округляется до ближайшего, привязан к четному , обозначается $\operatorname {RN}$ . Если $\operatorname {ulp} (x)\leq 1$ , затем $\operatorname {RN} (x+1)>x$ . В противном случае, $\operatorname {RN} (x+1)=x$ или $\operatorname {RN} (x+1)=x+\operatorname {ulp} (x)$ , в зависимости от значения младшей значащей цифры и показателя степени $x$ . Это продемонстрировано в следующем коде Haskell , введенном в интерактивной командной строке: ^{[ нужна ссылка ]}

> until (\x -> x == x+1) (+1) 0 :: Float
1.6777216e7
> it-1
1.6777215e7
> it+1
1.6777216e7

Здесь мы начинаем с 0 в одинарной точности (binary32) и неоднократно добавляем 1, пока операция не изменит значение. Поскольку мантисса числа одинарной точности содержит 24 бита, первое целое число, которое не совсем представимо, равно 2. ²⁴+1, и это значение округляется до 2 ²⁴ округляется до ближайшего, привязывается к четному. Таким образом, результат равен 2 ²⁴.

Пример 2

В следующем примере на Java аппроксимируется $число π$ как значение с плавающей запятой путем нахождения двух двойных значений, заключенных в скобки. $\pi$ : $p_{0}<\pi <p_{1}$ .

// π with 20 decimal digits
BigDecimal π = new BigDecimal("3.14159265358979323846");

// truncate to a double floating point
double p0 = π.doubleValue();
// -> 3.141592653589793  (hex: 0x1.921fb54442d18p1)

// p0 is smaller than π, so find next number representable as double
double p1 = Math.nextUp(p0);
// -> 3.1415926535897936 (hex: 0x1.921fb54442d19p1)

Затем $\operatorname {ulp} (\pi )$ определяется как $\operatorname {ulp} (\pi )=p_{1}-p_{0}$ .

// ulp(π) is the difference between p1 and p0
BigDecimal ulp = new BigDecimal(p1).subtract(new BigDecimal(p0));
// -> 4.44089209850062616169452667236328125E-16
// (this is precisely 2**(-51))

// same result when using the standard library function
double ulpMath = Math.ulp(p0);
// -> 4.440892098500626E-16 (hex: 0x1.0p-51)

Пример 3

Другой пример на Python , также вводимый в интерактивной командной строке:

>>> x = 1.0
>>> p = 0
>>> while x != x + 1:
...   x = x * 2
...   p = p + 1
... 
>>> x
9007199254740992.0
>>> p
53
>>> x + 2 + 1
9007199254740996.0

В этом случае мы начинаем с x = 1 и несколько раз удваивать его, пока x = x + 1. Аналогично примеру 1, результат равен 2 ⁵³ потому что формат с плавающей запятой двойной точности использует 53-битное мантиссу.

Языковая поддержка

Библиотеки Boost C++ предоставляют функции boost::math::float_next, boost::math::float_prior, boost::math::nextafter и boost::math::float_advance для получения близлежащих (и удаленных) значений с плавающей запятой, ^[7] и boost::math::float_distance(a, b) для вычисления расстояния с плавающей запятой между двумя двойными значениями. ^[8]

Библиотека языка C предоставляет функции для вычисления следующего числа с плавающей запятой в заданном направлении: nextafterf и nexttowardf для float, nextafter и nexttoward для double, nextafterl и nexttowardl для long double, заявленный в <math.h>. Он также предоставляет макросы FLT_EPSILON, DBL_EPSILON, LDBL_EPSILON, которые представляют собой положительную разницу между 1,0 и следующим большим представимым числом соответствующего типа (т. е. единицей). ^[9]

Стандартная библиотека Java предоставляет функции Math.ulp(double) и Math.ulp(float). Они были представлены в Java 1.5.

Стандартная библиотека Swift обеспечивает доступ к следующему числу с плавающей запятой в некотором заданном направлении через свойства экземпляра. nextDown и nextUp. Он также предоставляет свойство экземпляра ulp и свойство типа ulpOfOne (что соответствует макросам C, таким как FLT_EPSILON^[10]) для типов Swift с плавающей запятой. ^[11]

См. также

ИЭЭЭ 754
ISO/IEC 10967 , часть 1 требует функции ulp.
Младший бит (LSB)
Машина эпсилон
Ошибка округления

Ссылки

^ Гольдберг, Дэвид (март 1991 г.). «Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой» (PDF) . Обзоры вычислительной техники ACM . 23 (1): 5–48. дои : 10.1145/103162.103163 . S2CID 222008826 . Архивировано (PDF) из оригинала 20 июля 2006 г. Проверено 20 января 2016 г. ( [1] , [2] , [3] ).
^ Jump up to: Перейти обратно: ^а ^б Мюллер, Жан-Мишель; Бруни, Николас; из Динешена, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018) [2010]. Справочник по арифметике с плавающей запятой (2-е изд.). Биркхойзер . дои : 10.1007/978-3-319-76526-6 . ISBN 978-3-319-76525-9 .
^ Харрисон, Джон. «Теория арифметики с плавающей запятой, проверяемая машиной» . Проверено 17 июля 2013 г.
^ Мюллер, Жан-Мишель (2005–11). «Об определении ulp(x)». Технический отчет INRIA 5504. Транзакции ACM в математическом программном обеспечении, Vol. V, № N, ноябрь 2005 г. Получено в 2012–2003 гг. по адресу http://ljk.imag.fr/membres/Carine.Lucas/TPScilab/JMMuller/ulp-toms.pdf .
^ Кахан, Уильям. «Логарифм, слишком умный наполовину» . Проверено 14 ноября 2008 г.
^ Бризебар, Николя; Анро, Гийом; Мюллер, Жан-Мишель; Циммерманн, Пол (май 2024 г.). «Правильно округленная оценка функции: почему, как и какой ценой?» .
^ Увеличьте float_advance .
^ Увеличьте float_distance .
^ Спецификация ISO/IEC 9899:1999 (PDF) . п. 237, §7.12.11.3 Следующие функции и §7.12.11.4 Следующие функции .
^ «ulpOfOne — FloatingPoint | Документация разработчика Apple» . Apple Inc. Apple Inc. Проверено 18 августа 2019 г.
^ «FloatingPoint — Стандартная библиотека Swift | Документация разработчика Apple» . Apple Inc. Apple Inc. Проверено 18 августа 2019 г.

Библиография

Гольдберг, Дэвид (1991–03). «Ошибка округления» в книге «Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой». Computing Surveys, ACM, март 1991 г. Получено с http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html#689 .
Мюллер, Жан-Мишель (2010). Справочник по арифметике с плавающей запятой . Бостон: Биркхойзер. стр. 32–37. ISBN 978-0-8176-4704-9 .

[1] Гольдберг, Дэвид (март 1991 г.). «Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой» (PDF) . Обзоры вычислительной техники ACM . 23 (1): 5–48. дои : 10.1145/103162.103163 . S2CID 222008826 . Архивировано (PDF) из оригинала 20 июля 2006 г. Проверено 20 января 2016 г. ( [1] , [2] , [3] ).

[hfpa2018-2] Jump up to: Перейти обратно: ^а ^б Мюллер, Жан-Мишель; Бруни, Николас; из Динешена, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018) [2010]. Справочник по арифметике с плавающей запятой (2-е изд.). Биркхойзер . дои : 10.1007/978-3-319-76526-6 . ISBN 978-3-319-76525-9 .

[3] Харрисон, Джон. «Теория арифметики с плавающей запятой, проверяемая машиной» . Проверено 17 июля 2013 г.

[4] Мюллер, Жан-Мишель (2005–11). «Об определении ulp(x)». Технический отчет INRIA 5504. Транзакции ACM в математическом программном обеспечении, Vol. V, № N, ноябрь 2005 г. Получено в 2012–2003 гг. по адресу http://ljk.imag.fr/membres/Carine.Lucas/TPScilab/JMMuller/ulp-toms.pdf .

[5] Кахан, Уильям. «Логарифм, слишком умный наполовину» . Проверено 14 ноября 2008 г.

[6] Бризебар, Николя; Анро, Гийом; Мюллер, Жан-Мишель; Циммерманн, Пол (май 2024 г.). «Правильно округленная оценка функции: почему, как и какой ценой?» .

[Boost_advance-7] Увеличьте float_advance .

[Boost_float_distance-8] Увеличьте float_distance .

[c99-9] Спецификация ISO/IEC 9899:1999 (PDF) . п. 237, §7.12.11.3 Следующие функции и §7.12.11.4 Следующие функции .

[10] «ulpOfOne — FloatingPoint | Документация разработчика Apple» . Apple Inc. Apple Inc. Проверено 18 августа 2019 г.

[11] «FloatingPoint — Стандартная библиотека Swift | Документация разработчика Apple» . Apple Inc. Apple Inc. Проверено 18 августа 2019 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]