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

62

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

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

NMAT
источник
28
Если быть точным, то это не ошибка, вызванная округлением, о котором беспокоится большинство людей, а тот факт, что двоичное округление с плавающей точкой ведет себя не интуитивно. Переключение на десятичное представление может сделать округление более интуитивно понятным, но взамен вы почти всегда увеличите относительную ошибку (или вам придется увеличить пространство для компенсации).
Даниэль Приден
12
Моя попытка выяснить наиболее распространенные заблуждения: плавающая
точка-
Я думаю, что @DanielPryden означает: «Переключение на представление [с фиксированной запятой] может сделать округление более интуитивным…» . что вызывает проблемы с округлением, будь то фиксированные числа или числа с плавающей точкой, это конечная ширина слова любого из них. просто с плавающей точкой величина ошибки округления обычно остается примерно пропорциональной величине округляемого числа. (кроме случаев, когда вы получаете действительно маленькие и «денормализованные» числа.)
Роберт Бристоу-Джонсон
@ Роберт: Это не совсем то, что я имел в виду. «Ошибка», с которой сталкивается большинство людей с плавающей запятой, не имеет ничего общего с плавающей запятой как таковой, это основа. IEEE-754 плавает и удваивает, использует показатель степени в основании 2, что означает, что дробные числа округляются до отрицательных степеней двух (1/2, 1/16, 1/1024 и т. Д.), А не отрицательных степеней 10 (1 / 10, 1/1000 и т. Д.) Это приводит к неинтуитивным результатам, таким как округление 0,1 до 0,1000001 и аналогичные проблемы.
Даниэль Приден
Вы можете использовать числа с плавающей точкой в ​​базе 10 - так decimalработает тип .NET . Фиксированная точка, с другой стороны, отличается. Пока ваш диапазон ограничен, фиксированная точка является хорошим ответом. Но ограничительный диапазон делает фиксированную точку непригодной для многих математических приложений, и в результате реализации чисел с фиксированной точкой часто не оптимизируются аппаратно.
Даниэль Приден

Ответы:

82

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

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

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

Торстен Мюллер
источник
12
Пятно на. Но я также хотел бы отметить, что некоторые числа, заканчивающиеся на десятичные, не заканчиваются на двоичные. В частности, 0,1 - это повторяющееся число в двоичном коде, поэтому двоичное число с плавающей запятой не может точно представлять 0,1.
Джек Эйдли
4
Плавающие точки полезны не только для многих десятичных знаков. 32-разрядные целые числа могут насчитывать только около 4 миллиардов, но 32-разрядное число с плавающей запятой может быть почти бесконечно большим.
Абхи Бекерт
7
В частности, дроби, которые мы можем выразить как конечные десятичные дроби, - это те, у которых первичная факторизация знаменателей содержит только 2 и 5 (например, мы можем выразить 3/10 и 7/25, но не 11/18). Когда мы переходим к двоичному, мы теряем коэффициент 5, так что только двоичные рациональные числа (например, 1/4, 3/128) могут быть точно выражены.
Дэвид Чжан
70

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

Марк Бут
источник
1
Как автор этих статей я хотел бы отметить, что я создал их интерактивные версии в своем блоге www.thusspakeak.com, начиная с thusspakeak.com/ak/2013/06 .
так говорил
Спасибо @ thusspakea.k. Я добавил примечание к своему ответу, и эти интерактивные элементы работают очень хорошо.
Марк Бут
12

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

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

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

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

Рассмотрим вычисление степеней (взаимного) золотого сечения φ=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 , вы заметите несколько сообщений об ошибках, предупреждающих о появлении плохих условий.)

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

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


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

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


источник
9

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

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

чокнутый урод
источник
11
Не совсем верно: 0,5 и 0,25 могут быть выражены в основании 2. Я думаю, что вы имеете в виду «не все десятичные числа базы 10».
Скотт Уитлок
3
Точнее. Не все дробные числа могут быть представлены точно, используя запись с плавающей запятой (то есть с. У и базы 2 и базы 10 есть эта точная проблема). Попробуй и сделай 9*3.3333333в десятичном виде и сопоставь это с9*3 1/3
Мартин Йорк
1
Это наиболее распространенный источник путаницы с плавающей точкой. .1 + .1 != .2потому что используется двоичное кодирование с плавающей точкой, а не десятичное.
Шон Макмиллан
@SeanMcMillan: И 1.0/3.0*3.0 != 1.0поскольку используется двоичное кодирование с плавающей точкой, а не триное.
Кит Томпсон
8

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

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

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

MSalters
источник
2
Хуже того, хотя бесконечное (счетно бесконечное) количество памяти позволило бы представлять все рациональные числа, этого недостаточно для представления действительных чисел. Еще хуже то, что почти все действительные числа не являются вычислимыми числами. Лучшее, что мы можем сделать с ограниченным объемом памяти, - это приблизить подмножество действительных чисел с конечным диапазоном.
Дэвид Хаммен
4
@ Кевин: Вы говорите о вычислимых числах, которые представляют собой крошечное подмножество (подмножество с нулевой мерой) действительных чисел.
Дэвид Хаммен
1
+1 за самое простое объяснение: вы пытаетесь представить бесконечное количество чисел с конечным числом битов.
Раку
1
@DavidHammen: вычислимые числа являются крошечным подмножеством (нулевой меры) действительных чисел, но каждое число, с которым вы когда-либо будете работать в программе, по определению вычислимо.
Кит Томпсон
3
@ Джорджио: Если вы выберете правильное представление, квадратный корень из 2 будет представлен, например, в виде строки "√2". (Мой старый калькулятор HP-48 был в состоянии сделать именно это, и квадрат этого значения привел точно 2.0.) Существует только счетная бесконечность представимых действительных чисел для любого конечного представления - но никакие вычисления не могут дать число, которое не в принципе представительный. На практике двоичные числа с плавающей запятой резко ограничивают набор представимых чисел, обеспечивая невероятную скорость и крошечное хранение по сравнению с символическими представлениями.
Кит Томпсон
-2

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

$$ \ 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 $ и ноль, который отменяет его внутри. но это интегратор, и любое дерьмо, которое интегрируется и не удаляется полностью, будет существовать в сумме интегратора навсегда. Здесь фиксированная точка не имеет той же проблемы, что и числа с плавающей точкой.

Роберт Бристоу-Джонсон
источник
эй, разве математика $ LaTeX $ не работает на форуме prog.SE ??? это действительно глупо, если это не так.
Роберт Бристоу-Джонсон
1
Смотрите это на meta.SO и связанных вопросах
AakashM