Что вызывает ошибки округления с плавающей запятой?

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

Однако я не знаю, каковы причины этой неточности. Почему существует так много проблем округления с числами с плавающей запятой?

Это потому, что некоторые дроби нуждаются в очень большом (или даже бесконечном) количестве мест, которые можно выразить без округления. Это верно как для десятичной записи, так и для двоичной или любой другой. Если вы захотите ограничить количество десятичных разрядов, которые будут использоваться для ваших расчетов (и не будете делать вычисления в дробной записи), вам придется округлить даже простое выражение до 1/3 + 1/3. Вместо записи 2/3 в результате вы должны будете написать 0,33333 + 0,33333 = 0,66666, что не совпадает с 2/3.

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

Что каждый ученый должен знать об арифметике с плавающей точкой

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

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

Важно понять, когда они могут вызвать проблемы, и предпринять шаги для снижения рисков .

В дополнение к важной статье Дэвида Голдберга « Что должен знать каждый компьютерщик» об арифметике с плавающей запятой (переизданной Sun / Oracle в качестве приложения к их Руководству по числовым вычислениям ), о которой упоминал Торстен , журнал « Перегрузка» ACCU показал отличную работу. серия статей Ричарда Харриса о блюзе с плавающей точкой .

Серия началась с

• Вы будете думать! вперегрузке № 99( pdf , p5-10):

Численные вычисления имеют много подводных камней. Ричард Харрис начинает искать серебряную пулю.

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

Настолько, что некоторые программисты, случайно наткнувшись на него в лесах арифметики IEEE 754, советуют своим товарищам не путешествовать по этой прекрасной земле.

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

Ричард начинает с объяснения таксономии действительных чисел, рациональных, иррациональных, алгебраических и трансцендентных. Затем он продолжает объяснять представление IEEE754, прежде чем перейти к ошибке отмены и порядку проблем выполнения.

Если вы читаете не глубже этого, у вас будет отличное представление о проблемах, связанных с числами с плавающей запятой.

Если вы хотите узнать больше, он продолжает

• Почему Fixed Point не излечит ваш блюз с плавающей точкой приперегрузке # 100( pdf , p15-22)
• Почему Rationals не вылечит ваш блюз с плавающей точкой вперегрузке # 101( pdf , p9-13)
• Почему компьютерная алгебра не вылечит ваш блюз с плавающей точкой вперегрузке # 102( pdf , p9-14).
• Почему интервальная арифметика не вылечит ваш блюз с плавающей точкой приперегрузке 103( pdf , p19-24)

Затем он переключается на попытки помочь вам вылечить ваш Calculus Blues

• Почему [Вставьте Алгоритм Здесь] не вылечит ваш Исчисление Блюза вПерегрузке 104( pdf , p22-24).
• Почему конечные различия не вылечат исчисление блюза вперегрузке 105( pdf , p5-12).
• Почему полиномиальная аппроксимация не излечит исчисление блюза приперегрузке 106( pdf , p16-25).
• Почему компьютерная алгебра не вылечит исчисление блюза приперегрузке 107( pdf , p15-20).

и наконец, что не менее важно, есть

• Почему автоматическое дифференцирование не излечит исчисление блюза приперегрузке 108( pdf , p4-11).

Целый ряд статей стоит того, чтобы их изучить, и в общей сложности на 66 страницах они все же меньше, чем 77 страниц статьи Гольдберга .

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

Как говорил Спак в комментариях:

Как автор этих статей я хотел бы отметить, что я создал их интерактивные версии в своем блоге www.thusspakeak.com, начиная с thusspakeak.com/ak/2013/06 .

Ну, у Торстена есть окончательная связь . Я бы добавил:

Любая форма представления будет иметь некоторую ошибку округления для некоторого числа. Попробуйте выразить 1/3 в IEEE с плавающей запятой или в десятичной. Никто не может сделать это точно. Это выходит за рамки ответа на ваш вопрос, но я успешно использовал это правило:

• Храните введенные пользователем значения в десятичном формате (поскольку они почти наверняка вводили его в десятичном представлении - очень немногие пользователи будут использовать двоичный или шестнадцатеричный). Таким образом, у вас всегда будет точное введенное пользователем представление.
• Если вам нужно хранить введенные пользователем дроби, сохраните числитель и знаменатель (также в десятичном формате)
• Если у вас есть система с несколькими единицами измерения для одного и того же количества (например, по Цельсию / Фаренгейту), и пользователь может ввести и то, и другое, сохраните введенное значение и единицы, в которые они ввели его. Не пытайтесь преобразовать и сохранить как одно представление, если вы не можете сделать это без потери точности / точности. Используйте сохраненное значение и единицы во всех расчетах.
• Сохраните сгенерированные машиной значения в плавающей точке IEEE (это могут быть числа, сгенерированные электронным измерительным устройством, например, аналоговым датчиком с аналого-цифровым преобразователем, или необоснованный результат расчета). Обратите внимание, что это не применимо, если вы читаете датчик через последовательное соединение, и оно уже дает вам значение в десятичном формате (например, 18,2 C).
• Сохраняйте пользовательские итоги и т. Д. В десятичном виде (например, остаток на банковском счете). Округлите соответственно, но используйте это значение как окончательное значение для всех будущих вычислений.

Кажется, что до сих пор не было упомянуто о понятиях неустойчивого алгоритма и плохо обусловленной проблемы . Сначала я расскажу о первом, так как это кажется более частой ошибкой для начинающих нумераторов.

Рассмотрим вычисление степеней (взаимного) золотого сечения φ=0.61803…; Один из возможных способов - использовать формулу рекурсии φ^n=φ^(n-2)-φ^(n-1), начиная с φ^0=1и φ^1=φ. Если вы выполните эту рекурсию в своей любимой вычислительной среде и сравните результаты с точно оцененными возможностями, вы обнаружите медленную эрозию значительных цифр. Вот что происходит, например, в Mathematica :

ph = N[1/GoldenRatio];  
Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51]  
{0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, 
-2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 
1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, 
-5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 
2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, 
-9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 
3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, 
-1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 
6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, 
-2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 
1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, 
-5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 
2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, 
-9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 
3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, 
-1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 
7.136559332847351*^-7, -1.1547195563277288*^-6}

Предполагаемый результат для φ^41имеет неправильный знак, и даже ранее, вычисленные и фактические значения для φ^39общего не имеют общих цифр ( 3.484899258054952* ^ - 9 for the computed version against the true value7.071019424062048 *^-9). Алгоритм, таким образом, нестабилен, и не следует использовать эту формулу рекурсии в неточной арифметике. Это связано с природой формулы рекурсии: для этой рекурсии существует «затухающее» и «растущее» решение, и попытка вычислить «затухающее» решение путем прямого решения, когда есть альтернативное «растущее» решение, требует для численного горя. Таким образом, следует убедиться, что его / ее численные алгоритмы стабильны.

Теперь о понятии плохо обусловленной проблемы: даже если может существовать устойчивый способ сделать что-то численно, вполне может оказаться, что проблема, с которой вы столкнулись, просто не может быть решена вашим алгоритмом. Это вина самой проблемы, а не метод решения. Каноническим примером в числовом выражении является решение линейных уравнений с использованием так называемой «матрицы Гильберта»:

Матрица является каноническим примером плохо обусловленной матрицы: попытка найти систему с большой матрицей Гильберта может привести к неточному решению.

Вот демонстрация Mathematica : сравните результаты точной арифметики

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}]
{{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 
  1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1,
   1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 
  1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}

и неточная арифметика

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}]
{{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.},  
  {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, 
  {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.},  
  {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 
  0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 
  1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 
  0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 
  1.00342}}

(Если вы попробовали это в Mathematica , вы заметите несколько сообщений об ошибках, предупреждающих о появлении плохих условий.)

В обоих случаях простое повышение точности не является лекарством; это только задержит неизбежное размывание цифр.

Это то, с чем вы можете столкнуться. Решения могут быть трудными: во-первых, вы либо возвращаетесь к чертежной доске, либо просматриваете журналы / книги / что угодно, чтобы найти, если кто-то еще придумал лучшее решение, чем вы; во-вторых, вы либо сдаетесь, либо переформулируете свою проблему в более подходящую для себя сторону

Я оставлю вам цитату от Дайан О'Лири:

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

потому что десятичные числа базы 10 не могут быть выражены в базе 2

или, другими словами, 1/10 не может быть преобразовано в дробь со степенью 2 в знаменателе (что в сущности представляют собой числа с плавающей запятой)

В математике существует бесконечно много рациональных чисел. 32-разрядная переменная может иметь только 2 ³² различных значения, а 64-разрядная переменная - только 2 ⁶⁴ значения. Следовательно, существует бесконечно много рациональных чисел, которые не имеют точного представления.

Мы могли бы придумать схемы, которые позволили бы нам идеально представлять 1/3 или 1/100. Оказывается, что для многих практических целей это не очень полезно. Есть одно большое исключение: в финансах часто появляются десятичные дроби. Это в основном потому, что финансы - это, по сути, человеческая деятельность, а не физическая.

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

единственная действительно очевидная "проблема округления" с числами с плавающей точкой, о которой я думаю, это с фильтрами скользящих средних

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limit_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] - x [nN]) \ \ end {align} $$

чтобы сделать эту работу без накопления шума, вы должны убедиться, что $ x [n] $, который вы добавляете в текущие выборки, точно такой же, как $ x [nN] $, из которого вы вычтете $ N $ выборок в будущее. если это не так, то отличается то, что маленькая какашка застревает в линии задержки и никогда не выйдет. это потому, что этот фильтр скользящего среднего на самом деле построен с IIR, который имеет минимально устойчивый полюс в $ z = 1 $ и ноль, который отменяет его внутри. но это интегратор, и любое дерьмо, которое интегрируется и не удаляется полностью, будет существовать в сумме интегратора навсегда. Здесь фиксированная точка не имеет той же проблемы, что и числа с плавающей точкой.