Хабрахабр

[Перевод] Posit-арифметика: победа над floating point на его собственном поле. Часть 2

Часть 1

4. Количественное сравнение числовых систем

4.1. Определение десятичной точности

Если у нас есть пара чисел x и y (ненулевых и одного знака), расстояние между ними в порядках величин составляет $\mid log_( x / y )\mid$ десятичных порядков, это та же самая мера, которая определяет динамический диапазон между самым маленьким и самым большим представимым положительным числом x и y. Точность обратна ошибке. Это шкала децибел, долгое время используемая инженерами для выражения отношений, например, 10 децибел — это десятикратное отношение. Идеальным распределением десяти чисел между 1 и 10 в вещественной системе счисления было бы не равномерное распределение чисел по порядку от 1 до 10, а экспоненциальное: $1, 10^{1/10}, 10^{2/10},..., 10^{9/10}, 10$. Отношение 1db — это коэффициент около 1,26, если вы знаете значение с точностью 1db, вы имеете точность 1 десятичный знак. 30db означает коэффициент $10^3=1000$. Формула десятичной точности$log_{10}(1/\mid log_{10}(x/y)\mid)=-log_{10}(\mid log_{10}(x/y)\mid )$, где x и y — либо корректные значения, вычисленные с использованием систем округления, таких, какие используются в форматах float и posit, либо верхние и нижние границы, если используются строгие системы, использующие интервалы, или значения valid.
Если вы знаете величину с точностью 0,1 db, Это означает 2 знака точности, и т.п.

4.2. Определение множеств сравнения чисел float и posit

Мы можем создать масштабные модели чисел float и posit длиной по 8 бит каждое. Преимущество данного подхода в том, что 256 значений, это достаточно маленькое множество, чтобы мы могли проверить его полностью, и сравнить все $256^2$ вхождений в таблицах для операций сложения, вычитания, умножения и деления. Вещественные числа с точностью 1/4 имеют один знаковый бит, четыре бита экспоненты и три бита дробной части, и придерживаются всех правил стандарта IEEE 754. Наименьшее положительное число (денормализованное) равно 1/1024, наибольшее положительное равно 240, динамический диапазон ассиметричен и равен 5,1 десятичных порядков.14 битовых комбинаций представляют NaN.

Значений NaN нет. Сравнимое 8-битное posit использует es=1, имеет диапазон положительных чисел от 1/4096 до 4096, симметричный динамический диапазон 7,2 десятичных порядков. 7. Мы можем построить графики десятичной точности положительных чисел в обоих наборах, как показано на рис. Зазубренность графиков для обоих систем представляет собой логарифмическую аппроксимацию кусочно-линейной функции. Отметим, что значения, представленные числами posit, имеют на два десятичных порядка больший динамический диапазон, чем числа float, и точность такую же или больше для всех значений, кроме тех, где числа float близки к переполнению или антипереполнению. дальше идут значения NaN. У чисел float точность снижается только слева, на участке, близком к антиперепонению, справа функция обрывается, т.к. Числа posit имеют более симметрично уменьшающуюся по краям функцию точности.

7.
Рис. Сравнение десятичной точности чисел float и posit

4.3. Сравнение операций одного аргумента

4.3.1. Обратное значение

Для каждого возможного входного значения x функции 1/x, результат может точно соответствовать другому значению в данном множестве, или может быть округлён, в этом случае мы можем измерить десятичную ошибку, используя формулу из раздела 4.1, для чисел float, результат может привести к переполнению или NaN. См. рис. 8.

8. Рис. Количественное сравнение чисел float и posit при вычислении обратного значения

Числа posit превосходят float в большом числе случаев, и это превосходство сохраняется во всём диапазоне. Кривые на правом графике показывают величину ошибки при вычислении обратного значения, при этом числа float могут давать в результате NaN. Числа posit замкнуты относительно вычисления обратного значения. Вычисление обратного значения денормализованных чисел float приводит к переполнению, что приводит к бесконечному значению ошибки, и, конечно, аргумент NaN даёт обратное значение NaN.

4.3.2. Квадратный корень

Функция квадратного корня не приводит к переполнению или антипереполнению. Для отрицательных аргументов, и для NaN результат будет NaN. Вспомним, что у нас «масштабная модель» чисел float и posit, преимущества posit возрастают с увеличением точности данных. Для 64-битных float и posit, ошибка posit будет составлять около 1/30 ошибки float, вместо 1/2.

4.3.3. Квадрат

Другая распространённая унарная операция — это $x^2$. Переполнения и антипереполнения обычное дело при возведении float в квадрат. Почти для половины float возведение в квадрат не приводит к осмысленному результату, тогда как возведение числа posit в квадрат всегда даёт в результате число posit (квадрат беззнаковой бесконечности есть беззнаковая бесконечность).

9.
Рис. Количественное сравнение чисел float и posit при вычислении $\sqrt x$

10.
Рис. Количественное сравнение чисел float и posit при вычислении $x^2$

4.3.4. Логарифм по основанию 2

Мы также провели сравнение для покрытия функции логарифма по основанию 2, то есть процент случаев, при которых $log_2(x)$ может быть точно представлен, и если он не может быть точно представлен, сколько десятичных знаков мы теряем. Числа float имеют в этом случае единственное преимущество: с их помощью можно представить $log_2(0)$ как $-\infty$ и $log_2(\infty)$ как $\infty$, но это более чем компенсируется большим словарём целых степеней двойки для чисел posit.

11.
Рис. Количественное сравнение чисел float и posit при вычислении $log_2(x)$

Если вы можете вычислить $log_2(x)$, нужно только умножить результат на масштабирующий коэффициент, чтобы получить $ln(x)$ или $log_{10}(x)$ или логарифм с любым другим основанием. График похож на аналогичный для квадратного корня, примерно половина случаев даёт NaN в обоих случаях, но числа posit имеют вдвое меньшую потерю десятичной точности.

4.3.5. Экспонента, $2^x$

Аналогично, если вы можете вычислять $2^x$, вы можете легко с помощю масштабирующего коэффициента получить $e^x$ или $10^x$ и т.п. Числа posit имеют одно исключение, $2^x$ равно NaN, когда аргумент равен $\pm\infty$.

12.
Рис. Количественное сравнение чисел float и posit при вычислении $2^x$

В этом примере, только небольшое количество ошибок так же велико, как $log_{10}(24096)\approx1233$ десятичных порядков. Максимальные десятичные потери для чисел posit могут показаться большими, так как $2^{maxpos}$ будут округлены обратно до maxpos. Если вы можете не использовать настолько бльшие числа, числа posit по-прежнему выигрывают, потому что ошибки при маленьких значениях намного лучше. Решайте, что лучше: потерять свыше тысячи десятичны порядков, или потерять бесконечное количество десятичных порядков? Графики показывают, насколько числа posit более стабильны в терминах динамического диапазона, в котором результат имеет смысл, и имеют превосходство в точности в пределах этого диапазона. Во всех случаях, когда вы потеряете большое количество десятичных порядков при использовании чисел posit, входной аргумент лежит далеко за пределами того, что числа float могут даже выразить.

Мы сейчас обратим наше внимание на четыре элементарных арифметических действия, имеющие два аргумента: сложение, вычитание, умножение и деление. Для обычных унарных операций $1/x, \sqrt x, x^2, log_2(x)$ и $2^x$, числа posit всецело и неизменно более точны, чем числа float с тем же числом бит, и выдают осмысленный результат в широком динамическом диапазоне.

4.4. Сравнение операций двух аргументов

Мы можем использовать масштабную модель числовой системы для изучения арифметических операций двух аргументов, таких, как сложение, вычитание, умножение и деление. Для того, чтобы визуализировать 65536 результатов, мы делаем «график покрытия» 256*256, который наглядно показывает, какая доля результатов точна, неточна, вызывает переполнение, антипереполнение или NaN.

4.4.1. Сложение и вычитание

Так как $x − y = x + (− y )$ прекрасно работает как для float, так и для posit, нет необходимости изучать вычитание отдельно. Для операции сложения, мы вычисляем точное значение $z = x + y$, и сравниваем его с суммой, возвращённой в каждой из числовых систем. Может случиться, что результат неточный, тогда он должен быть округлён до ближайшего конечного ненулевого числа, может произойти переполнение или антипереполнение, или неопределённость вида $\infty-\infty$, которая даёт в результате NaN. Каждый из этих случаев отмечен цветом, и мы можем охватить всю таблицу сложения одним взглядом. В случае округления результатов, цвет изменяется от чёрного (точное значение) до фиолетового (точное значение для posit и float). Рис. 13 показывает, на что похож график покрытия для чисел float и unum. Как и с унарными операциями, но имея гораздо больше точек, мы можем сделать выводы о способности каждой числовой системы давать осмысленные и точные ответы:

13.
Рис. Полный график покрытия для сложения чисел float и posit

14.
Рис. Количественное сравнение чисел float и posit для сложения

Широкая чёрная диагональная полоса на графике покрытия для float гораздо шире, чем она будет для большей точности, потому что она представляет зону денормализованных чисел, в которой числа float отстоят друг от друга на равных промежутках, подобно числам с фиксированной точкой, такие числа составляют большую долю от общего числа только в случае 8-битных чисел. С первого взгляда становится очевидно, что числа posit имеет существенно больше точек на графике сложения, в которых результат точный.

4.4.2. Умножение

Мы используем похожий подход для сравнения того, насколько хорошо числа float и posit умножаются. В отличие от сложения, умножение может вызвать антипереполнение чисел float. «Постепенное антипереполнение», зона, которую вы можете видеть в центре на рис.15. слева. (имеется в виду денормализованные числа. прим. перев.) Без этой зоны, голубая зона антипереполнения имела бы форму ромба. График умножения для чисел posit менее разноцветный, что лучше. Только два пиксела подсвечены как NaN, близко к месту, гда находится нулевая метка осей (пикселы крайний слева в центре по вертикали, и внизу в центре по горизонтали. прим. перев.) Там находятся результаты умножения $\pm\infty\cdot 0=NaN$. Числа float имеют больше случаев, при которых произведение оказывается точным, но ужасной ценой. Как показано на рис.15, почти 1/4 всех произведений float приводит либо к переполнению, либо к антипереполнению, и эта доля не снижается при увеличении точности float.

Полный график покрытия для умножения чисел float и posit
Рис 15.

Для таких случаев (очень редких) погрешность составлят 3,6 десятичных порядка. Наихудший случай округления для чисел posit наступает при $maxpos \times maxpos$, которое округляется снова до maxpos. 16, числа posit существенно лучше, чем float, минимизируют ошибку умножения. Как показываетграфик на рис.

16.
Рис. Количественное сравнение чисел float и posit для умножения

Количественные показатели для деления практически такие же, как для умножения. График покрытия для операции деления похож на график для умножения, но зоны меняются местами, для экономии места, он не приведён здесь.

4.5. Сравнения чисел float и posit для оценки выражений

4.5.1. Тест “32-битный бюджет точности”

Тесты обычно делаются из расчёта минимального времени выполнения, и часто не дают полного представления, насколько точен результат. Другим типом теста является такой, при котором мы фиксируем бюджет погрешности, то есть число бит на переменную, и попробуем получить максимальную десятичную точность в результате. Вот пример выражения, которые мы можем использовать для сравнения числовых систем с бюджетом 32 бита на число:

8827196\dotsb$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/115/b52/815/115b5281555ab59a4503de16362142f5.svg" alt="$X=\left(\dfrac{27/10-e}{\pi-(\sqrt 2+\sqrt 3)}\right)^{67/16}=302.

Мы будем выделять неверные цифры оранжевым цветом. Правило состоит в том, что мы начинаем с наилучшего представления чисел $\pi$ и $e$, возможного в каждой из числовых систем, и представлений всех указанных целых чисел, и видим, сколько десятичных цифр совпадают с истинным значением X после выполнения девяти операций в выражении.

3 до 7. Несмотря на то, что 32-битные числа IEEE float имеют десятичную точность, которая колеблется в диапазоне от 7. Это одна из причин того, что пользователи испытывают необходимость в использовании 64-битных float везде, так как даже простые выражения подвержены риску потери точности так сильно, что результат может оказаться бесполезен. 6 десятичных порядков, накопление ошибок округления при вычислении X даёт ответ 302.912⋯, имеющий всего три верные цифры.

2 и 8. 32-битные числа posit имеют переменную десятичную точность, которая колеблется между 8. При вычислении X, они дают нам ответ 302. 5 десятичных порядков для чисел с абсолютным значением около 1. Также не забываем, что 32-битные числа posit имеют динамический диапазон более 144 десятичных разрядов, а 32-битные float имеют гораздо меньший динамический диапазон 83 разряда. 88231⋯, имеющий вдвое больше значащих цифр. Следовательно, дополнительная точность результата достигается не за счёт сужения динамического диапазона.

4.5.2. Тест с четырёхкратной точностью: задача Голдберга о тонком треугольнике

Есть классическая задача о «тонком треугольнике» [1]: найти площадь треугольника со сторонами a, b, c, когда две из сторон b и c всего на 3 единицы младшего разряда (Units in the Last Place, ULPs) длиннее, чем половина длинной стороны (рис. 17).

17.
Рис. Задача Голдберга о тонком треугольнике

Классическая формула для площади A использует проиежуточную переменную s:

$s=\frac{a+b+c}2;A=\sqrt{s(s-a)(s-b)(s-c)}$

Попробуем 128-битные (с четырёхкратной точностью) числа IEEE float, для которых $a=7,b=c=7/2+3\times 2^{− 111}$. Опасность в этой формуле заключается в том, что s очень близко к значению a, и вычисление $(s-a)$ учеличивает погрешность округления очень сильно. Но это делает треугольник высотой с дверной проём у вершины.) Мы также вычисляем значение A, используя 128-битные числа posit (es=7). (Если за единицу измерения принять световой год, то короткая сторона будет длиннее половины длинной стороны всего на 1/200 диаметра протона. Ниже приведены результаты:

14784204874900425235885265494550774498\dots \times 10^{−16} \\ \textrm{128-bit IEEE float:} & 3.\color{orange}{63481490842332134725920516158057682788}\dots \times 10^{− 16}\\ \textrm{128-bit posit:} & 3. $$display$$\begin{matrix} \textrm{Верное значение:} & 3. 147842048749004252358852654945507744\color{orange}{39} \dots \times 10^{−16} \end{matrix}$$display$$

8 десятичных цифр точности больше по сравнению с float четырёхкратной точности в широком динамическом диапазоне: от $2\times 10^{− 270}$ до $5 \times 10^{− 269}$. Числа posit имеют до 1. Интересно также отметить, что ответ в формате posit будет более точным, чем в формате float, даже если мы в конце скорвертируем его в 16-битный posit. Этого достаточно для предотвращения катастрофических последствий усиления погрешности в данном конкретном случае.

4.5.3. Решение квадратного уравнения

Существует классический приём, предназначенный для того, чтобы избежать ошибки округления при вычислении корней $r_1$, $r_2$ уравнения $ax^2+bx+c=0$, используя обычную формулу $r_1,r_2=(-b\pm \sqrt {b^2-4ac})/(2a)$, когда b намного больше, чем a и c, что приводит к пропаданию цифр слева, так как $\sqrt {b^2-4ac}$ очень близко к b. Но вместо того, чтобы заставлять программистов запоминать мистические приёмы, возможно, лучше, чтобы posit сделал вычисление безопасным при использовании простой формулы из учебника. Положим $a=3,b=100,c=2$ и сравним результат в формате 32-битного float и posit.

Решение квадратного уравнения
Таблица 5.

Численно неустойчивый корень — $r_1$, но отметим, что 32-битный posit даёт 6 верных цифр вместо 4-х для float.

4.6. Сравнение систем floats и Posit для классического теста LINPACK

Основным методом оценки суперкомпьютеров долгое время было решение $n\times n$ системы линейных уравнений $\mathbf Ax=b$. А именно, тест заполняет матрицу A псевдослучайными числами от 0 до 1, и вектор b суммами строк A. Это означает, что решением x будет вектор, состоящий из единиц. Тест вычисляет норму вычетов $\|\mathbf Ax-b\|$ для проверки правильности, хотя нет жёстко установленного количества цифр, которые должны быть верными в ответе. Для теста типична потеря нескольких цифр точности, и обычно используются 64-битные float (не обязательно IEEE). Изначально тест предусматривал n=100, но этот размер оказался слишком мал для самых быстрых суперкомпьютеров, поэтому n было увеличено до 300, затем до 1000, и, наконец (с подачи первого автора), тест стал масштабируемым, и выдаёт количество операций в секунду, исходя из того, что тест выполняет $\frac {2}{3}n^3+2n^2$ операций умножения и сложения.

Такая ошибка может быть устранена, если мы найдём, какием вхождения в A вносят в сумму 1 бит, лежащий за пределами возможной точности, и установим этот бит в 0. Сравнивая posit и float, мы отметили небольшой недостаток теста: ответ в общем случае не является последовательностью единиц, из-за ошибок округления сумм в строках. Для исходного варианта задачи, с размером 100х100, 64-битные IEEE float дают ответ такого вида: Это даст нам уверенность, что сумма строки A представима без округления, и что ответ x на самом деле является вектором, состоящим из единиц.

9999999999999633626401873698341660201549530029296875
1. 0. 000000000000022648549702353193424642086029052734375 0000000000000011102230246251565404236316680908203125
$\vdots$
1.

С числами posit, мы можем сделать замечательную вещь. Ни одно из 100 чисел не является верным; они близки к 1, но никогда не равны 1. Затем решим $\mathbf Ax'=r$ (используя уже обработанное $\mathbf A$) и используем $x'$ для коррекции: $x \leftarrow x-x'$. Использовав 32-битные числа posit и тот же самый алгоритм, вычислим вычет $r = \mathbf Ax − b$, используя операцию слияния — скалярное произведение. Могут ли правила LINPACK запретить использовать новый 32-битный тип чисел, использование которого позволяет достичь совершенного результата с нулевой ошибкой, или продолжат настаивать на использовании 64-битного float, который этого не позволяет? Результатом является беспреценднтно точный для теста LINPACK ответ: $\{1, 1,...,1\}$. Тем же, кому нужно решение систем линейных уравнений для решения реальных задач, а не сравнение скорости суперкомпьютеров, posit предлагает ошеломляющие преимущества. Это решение будут принимать те, кто отвечает за этот тест.

5. Заключение

Числа posit имеют большую точность, больший динамический диапазон и большее покрытие. Posit побеждает float в его собственной игре: с его помощью можно выполнять вычисления и уменьшать ошибки округления. Так как пропускная способность систем ограничена, использование операндов меньшего размера означает большую скорость и меньшую потребляемую мощность.
Так как они работают как float, а не как интервальная система, они могут рассматриваться как прямая замена float, как и было продемонстрировано здесь. Они могут использоваться для получения лучших результатов, чем float той же разрядности, или (что может быть ещё большим конкурентным преимуществом), тех же результатов при меньшей разрядности. Комбинированные операции (fused operations), доступные в posit, предоставляют мощное средство для предотвращения накопления ошибок округления, и в некоторых случаях позволяют безопасно использовать 32-битные числа posit вместо 64-битных float в приложениях, требующих высокую производительность. Если алгоритм, использующий float, проходит тесты, и время и стабильность «достаточно хороши», то с posit он будет работать ещё лучше. Аппаратная поддержка posit даст нам эквивалент одного или двух шагов закона Мура, без необходимости уменьшать размер транзистора или повышать стоимость. Это в общем случае повысит производительность приложения в 2-4 раза, и сокращает потребляемую мощность, экономит энергию и снижает стоимость хранения данных. Числа posit проще и элегантнее, чем float, и позволяют сократить количество аппаратуры для их поддержки. В отличие от float, система posit даёт побитовую воспроизводимость результатов на разных системах, избавляя нас от главного недостатка стандарта IEEE 754. Хотя числа float сейчас распространены повсеместно, числа posit вскоре могут сделать их устарешими.

Ссылки:

1. David Goldberg. What every computer scientist should know about floating-point arithmetic.
ACM Computing Surveys (CSUR), 23(1):5–48, 1991. DOI: doi:10.1145/103162.103163.
2. John L Gustafson. The End of Error: Unum Computing, volume 24. CRC Press, 2015.
3. John L Gustafson. Beyond Floating Point: Next Generation Computer Arithmetic. Stanford Seminar: https://www.youtube.com/watch?v=aP0Y1uAA-2Y, 2016. full transcription
available at http://www.johngustafson.net/pdfs/DebateTranscription.pdf.
4. John L Gustafson. A radical approach to computation with real numbers. Supercomputing
Frontiers and Innovations, 3(2):38–53, 2016. doi:http://dx.doi.org/10.14529/jsfi160203.
5. John L Gustafson. The Great Debate @ ARITH23. https://www.youtube.com/watch?v=
KEAKYDyUua4, 2016. full transcription available at http://www.johngustafson.net/pdfs/
DebateTranscription.pdf.
6. Ulrich W Kulisch and Willard L Miranker. A new approach to scientific computation, volume 7. Elsevier, 2014.
7. More Sites. IEEE standard for floating-point arithmetic. IEEE Computer Society, 2008.
DOI:10.1109/IEEESTD.2008.4610935.
8. Isaac Yonemoto. https://github.com/interplanetary-robot/SigmoidNumbers

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть