Единица на последнем месте

Метрика точности с плавающей точкой

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

Определение

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

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

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

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

Примеры

Пример 1

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

> до ( \ x -> x == x + 1 ) ( + 1 ) 0 :: Плавающий         1.6777216e7> это - 11.6777215e7> это + 11.6777216e7

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

Пример 2

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

// π с 20 десятичными цифрами BigDecimal π = new BigDecimal ( "3.14159265358979323846" );    // усечение до числа с плавающей точкой double p0 = π . doubleValue (); // -> 3.141592653589793 (hex: 0x1.921fb54442d18p1)   // p0 меньше π, поэтому находим следующее число, представимое как double double p1 = Math . nextUp ( p0 ); // -> 3.1415926535897936 (hex: 0x1.921fb54442d19p1)   

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

// ulp(π) — это разница между p1 и p0 BigDecimal ulp = new BigDecimal ( p1 ) .subtract ( new BigDecimal ( p0 )); // -> 4.44089209850062616169452667236328125E-16 // (это точно 2**(-51))     // тот же результат при использовании стандартной библиотечной функции double ulpMath = Math . ulp ( p0 ); // -> 4.440892098500626E-16 (hex: 0x1.0p-51)   

Пример 3

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

>>> x  =  1,0 >>> p  =  0 >>> пока  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 и следующим большим представимым числом в соответствующем типе (т. е. ulp единицы). ^[9]

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

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

Смотрите также

• IEEE 754
• ISO/IEC 10967 , часть 1 требует функцию ulp
• Наименее значимый бит (LSB)
• Машинный эпсилон
• Ошибка округления

Ссылки

1. Голдберг, Дэвид (март 1991 г.). «Что каждый специалист по компьютерам должен знать об арифметике с плавающей точкой». ACM Computing Surveys . 23 (1): 5–48. doi : 10.1145/103162.103163 . S2CID  222008826.(С приложением «Различия между реализациями IEEE 754»: [1], [2]).
2. Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (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 Transactions on Mathematical Software, Vol. V, No. N, ноябрь 2005 г. Получено в 2012-03 с http://ljk.imag.fr/membres/Carine.Lucas/TPScilab/JMMuller/ulp-toms.pdf.
5. Кахан, Уильям. "Логарифм, слишком умный наполовину" . Получено 14 ноября 2008 г.
6. Бризебар, Николя; Анро, Гийом; Мюллер, Жан-Мишель; Циммерман, Поль (май 2024 г.). «Правильно округленная оценка функции: почему, как и какой ценой?».
7. Ускорение float_advance.
8. Увеличить float_distance.
9. Спецификация ISO/IEC 9899:1999 (PDF) . стр. 237, §7.12.11.3 Функции nextafter и §7.12.11.4 Функции nexttoward .
10. "ulpOfOne - FloatingPoint | Документация для разработчиков Apple". Apple Inc . Apple Inc . Получено 18 августа 2019 г. .
11. "FloatingPoint - Swift Standard Library | Документация для разработчиков 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). Справочник по арифметике с плавающей точкой . Бостон: Birkhäuser. С. 32–37. ISBN 978-0-8176-4704-9.