Устранение ошибок с плавающей запятой

Уменьшение ошибок с плавающей запятой — это минимизация ошибок, вызванных тем фактом, что действительные числа, как правило, не могут быть точно представлены в фиксированном пространстве. По определению, ошибку с плавающей запятой невозможно устранить, и в лучшем случае ею можно только управлять.

Уберто М. Сьерра отметил в своем патенте 1956 года «Средство арифметического управления с плавающей десятичной запятой для калькулятора»: ^[1]

Таким образом, при некоторых условиях большая часть значащих цифр данных может находиться за пределами емкости регистров. Поэтому полученный результат может иметь мало смысла, если не быть полностью ошибочным.

Z1 в , разработанный Конрадом Цузе 1936 году, был первым компьютером с арифметикой с плавающей запятой и, следовательно, был подвержен ошибкам с плавающей запятой. Однако первые компьютеры, время работы которых измерялось миллисекундами, были неспособны решать большие и сложные задачи. ^[2] и поэтому редко сталкивались с ошибками с плавающей запятой. Однако сегодня, когда производительность суперкомпьютерной системы измеряется петафлопсами , ошибка с плавающей запятой является серьезной проблемой для специалистов по решению вычислительных задач.

В следующих разделах описываются сильные и слабые стороны различных способов устранения ошибок с плавающей запятой.

Численный анализ ошибок

Хотя это и не является основным направлением численного анализа , ^[3]^[4]^: 5 Числовой анализ ошибок существует для анализа и минимизации ошибки округления с плавающей запятой.

Арифметика Монте-Карло

Анализ ошибок с помощью арифметики Монте-Карло осуществляется путем многократного внесения небольших ошибок в значения данных алгоритма и определения относительного влияния на результаты.

Расширение точности

Повышение точности — это использование более крупных представлений реальных значений, чем первоначально рассматриваемое. Стандарт IEEE 754 определяет точность как количество цифр, доступных для представления действительных чисел. Язык программирования может иметь одинарную точность (32 бита), двойную точность (64 бита) и учетверенную точность (128 бит). Хотя повышение точности делает последствия ошибки менее вероятными или менее важными, истинная точность результатов до сих пор неизвестна.

Арифметика переменной длины

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

Использование термина ошибки операции с плавающей запятой

Алгоритм с плавающей запятой, известный как TwoSum ^[5] или 2Sum , благодаря Кнуту и Мёллеру, и его более простая, но ограниченная версия FastTwoSum или Fast2Sum (3 операции вместо 6) позволяют получить (точный) член ошибки сложения с плавающей запятой, округленный до ближайшего. Можно также получить (точный) член ошибки умножения с плавающей запятой, округленный до ближайшего, за 2 операции с объединенным умножением и сложением (FMA) или за 17 операций, если FMA недоступен (с помощью алгоритма Деккера). Эти члены ошибок могут использоваться в алгоритмах для повышения точности конечного результата, например, с помощью разложений с плавающей запятой или компенсированных алгоритмов .

Операции, дающие результат сложения или умножения с плавающей запятой, округленного до ближайшего с его членом ошибки (но немного отличающийся от алгоритмов, упомянутых выше), были стандартизированы и рекомендованы в стандарте IEEE 754-2019.

Выбор другой системы счисления

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

Интервальная арифметика

Интервальная арифметика — это математический метод, используемый для ограничения ошибок округления и ошибок измерения в математических вычислениях . Значения — это интервалы, которые можно представить различными способами, например: ^[6]

inf-sup: нижняя и верхняя границы истинного значения;
Mid-rad: аппроксимация и граница ошибки (называемая средней точкой и радиусом интервала);
триплекс: аппроксимация, нижняя и верхняя границы ошибки.

«Вместо использования одного числа с плавающей запятой в качестве аппроксимации значения реальной переменной в исследуемой математической модели интервальная арифметика признает ограниченную точность, связывая с переменной набор действительных чисел в качестве возможных значений. Для простоты хранения и вычислений , эти множества ограничены интервалами». ^[7]

Оценка выражения интервальной арифметики может предоставить широкий диапазон значений. ^[7] и может серьезно переоценить истинные границы погрешности. ^[8]^: 8

Унумы Густавсона

Unums («универсальные числа») — это расширение арифметики переменной длины, предложенное Джоном Густавсоном . ^[9] Unums имеют поля переменной длины для экспоненты и длины мантиссы , а информация об ошибках передается в одном бите, ubit, представляющем возможную ошибку в младшем бите мантиссы ( ULP ). ^[9]^: 4

Эффективность unums подвергается сомнению Уильямом Кэханом . ^[8]

Ограниченная плавающая точка

Ограниченная плавающая запятая — это метод, предложенный и запатентованный Аланом Йоргенсеном. ^[10] Структура данных включает в себя стандартную структуру данных IEEE 754 и ее интерпретацию, а также информацию об ошибке между представленным истинным действительным значением и значением, сохраненным в представлении с плавающей запятой. ^[11]

Ограниченную плавающую запятую критиковали как производную от работы Густавсона по унумам и интервальной арифметике. ^[10]^[12]

Ссылки

^ «Средство управления арифметикой с плавающей десятичной запятой для калькулятора: патент США 3037701» . FreePatentsOnline.com . 05.06.1962 . Проверено 21 января 2022 г.
^ «История развития компьютеров и поколения компьютеров» . ВикиПедагог . Сентябрь 2014 года . Проверено 17 февраля 2018 г.
^ Трефетен, Ллойд Н. (1992). «Определение численного анализа» (PDF) . СИАМ . Проверено 16 февраля 2018 г.
^ Хайэм, Николас Джон (2002). Точность и устойчивость численных алгоритмов (2-е изд.). Общество промышленной и прикладной математики (SIAM). ISBN 978-0-89871-521-7 .
^ Ричард Шевчук, Джонатан (октябрь 1997 г.). «Адаптивная точная арифметика с плавающей запятой и быстрые устойчивые геометрические предикаты» (PDF) . Дискретная и вычислительная геометрия . 18 (3): 305–363. дои : 10.1007/PL00009321 . S2CID 189937041 . Проверено 14 ноября 2022 г.
^ «Стандарт IEEE для интервальной арифметики» . IEEE СТД 1788-2015 : 1–97. 30 июня 2015 г. doi : 10.1109/IEESTD.2015.7140721 . ISBN 978-0-7381-9720-3 .
^ Jump up to: ^а ^б Хики, Т.; Джу, К.; ван Эмден, штат Миннесота (сентябрь 2001 г.). «Интервальная арифметика: от принципов к реализации» (PDF) . Журнал АКМ . 48 (5): 1038–1068. CiteSeerX 10.1.1.43.8001 . дои : 10.1145/502102.502106 . S2CID 15105694 . Проверено 16 февраля 2018 г.
^ Jump up to: ^а ^б Кахан, Уильям (июль 2016 г.). «Критика книги Джона Л. Густафсона КОНЕЦ ОШИБКИ — Unum Computation и его радикальный подход к вычислениям с действительными числами» (PDF) . Проверено 17 февраля 2018 г.
^ Jump up to: ^а ^б Густафсон, Джон Лерой (04 февраля 2016 г.) [05 февраля 2015 г.]. Конец ошибки: Unum Computing . Чепмен и Холл / CRC Вычислительная наука . Том. 24 (2-е исправленное издание, 1-е изд.). ЦРК Пресс . ISBN 978-1-4822-3986-7 . Проверено 30 мая 2016 г. [1] [2]
^ Jump up to: ^а ^б Трейдер, Тиффани (17 января 2018 г.). «Изобретатель утверждает, что решил проблему ошибок с плавающей запятой» . HPCwire . Проверено 01 марта 2022 г.
^ Патент США 11023230B2 , Йоргенсен, Алан А., «Устройство для расчета и сохранения границы ошибки во время операций с плавающей запятой и их методы», выдан 1 июня 2021 г.
^ «Решена ли десятилетняя проблема ошибок с плавающей запятой?» . внутриHPC . 17 января 2018 г. Проверено 01 марта 2022 г.

[1] «Средство управления арифметикой с плавающей десятичной запятой для калькулятора: патент США 3037701» . FreePatentsOnline.com . 05.06.1962 . Проверено 21 января 2022 г.

[2] «История развития компьютеров и поколения компьютеров» . ВикиПедагог . Сентябрь 2014 года . Проверено 17 февраля 2018 г.

[3] Трефетен, Ллойд Н. (1992). «Определение численного анализа» (PDF) . СИАМ . Проверено 16 февраля 2018 г.

[Higham1-4] Хайэм, Николас Джон (2002). Точность и устойчивость численных алгоритмов (2-е изд.). Общество промышленной и прикладной математики (SIAM). ISBN 978-0-89871-521-7 .

[5] Ричард Шевчук, Джонатан (октябрь 1997 г.). «Адаптивная точная арифметика с плавающей запятой и быстрые устойчивые геометрические предикаты» (PDF) . Дискретная и вычислительная геометрия . 18 (3): 305–363. дои : 10.1007/PL00009321 . S2CID 189937041 . Проверено 14 ноября 2022 г.

[IEEE_2015_1788-6] «Стандарт IEEE для интервальной арифметики» . IEEE СТД 1788-2015 : 1–97. 30 июня 2015 г. doi : 10.1109/IEESTD.2015.7140721 . ISBN 978-0-7381-9720-3 .

[Hickey-7] Jump up to: ^а ^б Хики, Т.; Джу, К.; ван Эмден, штат Миннесота (сентябрь 2001 г.). «Интервальная арифметика: от принципов к реализации» (PDF) . Журнал АКМ . 48 (5): 1038–1068. CiteSeerX 10.1.1.43.8001 . дои : 10.1145/502102.502106 . S2CID 15105694 . Проверено 16 февраля 2018 г.

[Kahan1-8] Jump up to: ^а ^б Кахан, Уильям (июль 2016 г.). «Критика книги Джона Л. Густафсона КОНЕЦ ОШИБКИ — Unum Computation и его радикальный подход к вычислениям с действительными числами» (PDF) . Проверено 17 февраля 2018 г.

[Gustafson-9] Jump up to: ^а ^б Густафсон, Джон Лерой (04 февраля 2016 г.) [05 февраля 2015 г.]. Конец ошибки: Unum Computing . Чепмен и Холл / CRC Вычислительная наука . Том. 24 (2-е исправленное издание, 1-е изд.). ЦРК Пресс . ISBN 978-1-4822-3986-7 . Проверено 30 мая 2016 г. [1] [2]

[HPCWire-10] Jump up to: ^а ^б Трейдер, Тиффани (17 января 2018 г.). «Изобретатель утверждает, что решил проблему ошибок с плавающей запятой» . HPCwire . Проверено 01 марта 2022 г.

[2021Patent-11] Патент США 11023230B2 , Йоргенсен, Алан А., «Устройство для расчета и сохранения границы ошибки во время операций с плавающей запятой и их методы», выдан 1 июня 2021 г.

[12] «Решена ли десятилетняя проблема ошибок с плавающей запятой?» . внутриHPC . 17 января 2018 г. Проверено 01 марта 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]