языковая независимость — не сломана ли математика с плавающей точкой?

0.1 + 0.2 == 0.3  ->  false

0.1 + 0.2         ->  0.30000000000000004

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

1. Обзор

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

2. Стандарты

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

В стандарте IEEE-754 разработчикам аппаратного обеспечения разрешается любое значение error / epsilon, если в последнем месте меньше половины одного модуля, а результат должен составлять менее половины одного модуля в последнем. место для одной операции. Это объясняет, почему при повторных операциях ошибки складываются. Для двойной точности IEEE-754 это 54-й бит, поскольку 53 бита используются для представления числовой части (нормализованной), также называемой мантиссой, числа с плавающей запятой (например, 5.3 в 5.3e5). В следующих разделах более подробно рассматриваются причины аппаратной ошибки при различных операциях с плавающей запятой.

3. Причина ошибки округления в делении

Основной причиной ошибки в делении с плавающей запятой являются алгоритмы деления, используемые для вычисления отношения. Большинство компьютерных систем вычисляют деление, используя умножение на обратное, главным образом в Z=X/Y, Z = X * (1/Y), Деление вычисляется итеративно, то есть каждый цикл вычисляет некоторые биты частного до тех пор, пока не будет достигнута желаемая точность, которая для IEEE-754 равна нулю с ошибкой менее одной единицы в последнем месте. Таблица обратных значений Y (1 / Y) называется таблицей выбора коэффициентов (QST) при медленном делении, а размер в битах таблицы коэффициентов выбора обычно равен ширине радиуса или числу битов. коэффициент, вычисленный в каждой итерации, плюс несколько защитных битов. Для стандарта IEEE-754 с двойной точностью (64-битная) это будет размер радиуса делителя плюс несколько защитных битов k, где k>=2, Так, например, типичная таблица выбора частного для делителя, который вычисляет 2 бита частного за раз (основание 4), будет 2+2= 4 биты (плюс несколько необязательных битов).

3.1 Ошибка округления деления: аппроксимация взаимности

То, что взаимные значения находятся в таблице выбора коэффициента, зависит от метод деления: медленное деление, такое как деление SRT, или быстрое деление, такое как деление Гольдшмидта; каждая запись модифицируется в соответствии с алгоритмом деления в попытке получить минимально возможную ошибку. В любом случае, однако, все взаимные приближения фактического взаимного и ввести некоторый элемент ошибки. И методы с медленным, и с быстрым делением вычисляют частное итеративно, то есть некоторое количество бит частного вычисляется на каждом шаге, затем результат вычитается из делимого, и делитель повторяет шаги, пока ошибка не станет меньше половины одного Блок на последнем месте. Методы медленного деления вычисляют фиксированное количество цифр отношения на каждом шаге и, как правило, дешевле в построении, а методы быстрого деления вычисляют переменное количество цифр на шаг и, как правило, стоят дороже. Наиболее важной частью методов деления является то, что большинство из них полагаются на повторное умножение на приближение о взаимности, поэтому они подвержены ошибкам.

4. Ошибки округления в других операциях: усечение

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

5. Повторные операции

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

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

6. Резюме

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

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

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

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

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

Теперь, как бы вы нарезали все ломтики таким образом, чтобы можно было получить одну десятую (0,1) или одну пятую (0,2) пиццы? На самом деле подумайте об этом и попробуйте решить это. Вы даже можете попробовать настоящую пиццу, если у вас под рукой мифическая прецизионная пиццерия. 🙂

---

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

Для чисел с двойной точностью (то есть точности, которая позволяет вдвое сократить пиццу в 53 раза), числа, которые сразу меньше и больше 0,1, составляют 0,09999999999999999167332731531132594682276248931884765625 и 0,1000000000000000055511151231257827021181583404541015625. Последнее немного ближе к 0,1, чем первое, поэтому числовой синтаксический анализатор, при вводе 0,1, предпочтителен последнему.

(Разница между этими двумя числами заключается в «наименьшем срезе», который мы должны решить либо включить, который вводит смещение вверх, либо исключить, который вводит смещение вниз. Техническим термином для этого наименьшего среза является ULP.)

В случае с 0,2 все числа одинаковы, только увеличены в 2 раза. Опять же, мы предпочитаем значение, немного превышающее 0,2.

Обратите внимание, что в обоих случаях аппроксимации для 0,1 и 0,2 имеют небольшое смещение вверх. Если мы добавим достаточное количество этих смещений, они будут отталкивать число все дальше и дальше от того, что мы хотим, и на самом деле, в случае 0,1 + 0,2, смещение достаточно велико, чтобы полученное число больше не было ближайшим числом до 0,3.

В частности, 0,1 + 0,2 действительно 0.1000000000000000055511151231257827021181583404541015625 + 0.200000000000000011102230246251565404236316680908203125 = 0.3000000000000000444089209850062616169452667236328125, тогда как число ближе к 0,3 фактически 0,299999999999999988897769753748434595763683319091796875.

---

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

(Первоначально опубликовано на Quora.)

Ошибки округления с плавающей точкой. 0,1 не может быть представлен так же точно в Base-2, как и в Base-10, из-за отсутствующего простого множителя, равного 5. Точно так же, как 1/3 принимает бесконечное число цифр для представления в десятичной форме, но равен «0,1» в Base-3, 0.1 принимает бесконечное количество цифр в base-2, а не в base-10. И у компьютеров нет бесконечного количества памяти.

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

Например:

var result = 1.0 + 2.0;     // result === 3.0 returns true

… вместо:

var result = 0.1 + 0.2;     // result === 0.3 returns false

Выражение 0.1 + 0.2 === 0.3 возвращается false в JavaScript, но, к счастью, целочисленная арифметика с плавающей точкой является точной, поэтому ошибок масштабирования можно избежать с помощью масштабирования.

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

---

¹ Дуглас Крокфорд: JavaScript: хорошие части: Приложение A — Ужасные части (стр. 105).

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

преамбула

Двоичный формат с плавающей запятой IEEE 754 (двоичный код 64) число представляет собой номер формы

значение = (-1) ^ с * (1 м₅₁м₅₀…м₂м₁м₀)₂ * 2^е-1023

в 64 битах:

• Первый бит это бит знака: 1 если число отрицательное, 0 иначе¹.
• Следующие 11 бит показатель степени, который смещение на 1023. Другими словами, после считывания показательных битов из числа с двойной точностью необходимо вычесть 1023, чтобы получить степень двойки.
• Остальные 52 бита являются мантисса (или мантисса). В мантиссе подразумевается 1. всегда² опущено, так как наиболее значимый бит любого двоичного значения 1,

¹ — IEEE 754 допускает концепцию подписанный ноль — +0 а также -0 трактуются по-разному: 1 / (+0) положительная бесконечность; 1 / (-0) отрицательная бесконечность. Для нулевых значений биты мантиссы и экспоненты равны нулю. Примечание: нулевые значения (+0 и -0) явно не классифицируются как денормальные².

² — Это не так для ненормальные числа, которые имеют показатель смещения, равный нулю (и подразумеваемый 0.). Диапазон денормальных чисел двойной точности равен d_мин ≤ | x | ≤ d_{Максимум}, где D_мин (наименьшее представимое ненулевое число) равно 2^{-1023 — 51} (≈ 4.94 * 10^-324) и г_{Максимум} (наибольшее денормальное число, для которого мантисса состоит полностью из 1с) 2^{-1023 + 1} — 2^{-1023 — 51} (≈ 2,225 * 10^-308).

---

Превращение числа с двойной точностью в двоичное

Существует много онлайн-конвертеров для преобразования числа с плавающей запятой двойной точности в двоичное (например, в binaryconvert.com), но здесь приведен пример кода C # для получения представления IEEE 754 для числа с двойной точностью (я разделяю эти три части двоеточиями (:):

public static string BinaryRepresentation(double value)
{
long valueInLongType = BitConverter.DoubleToInt64Bits(value);
string bits = Convert.ToString(valueInLongType, 2);
string leadingZeros = new string('0', 64 - bits.Length);
string binaryRepresentation = leadingZeros + bits;

string sign = binaryRepresentation[0].ToString();
string exponent = binaryRepresentation.Substring(1, 11);
string mantissa = binaryRepresentation.Substring(12);

return string.Format("{0}:{1}:{2}", sign, exponent, mantissa);
}

---

Приступая к делу: оригинальный вопрос

(Перейти к нижней части для версии TL; DR)

Катон Джонстон (задающий вопрос) спросил, почему 0,1 + 0,2! = 0,3.

Записанные в двоичном виде (с двоеточиями, разделяющими три части), представления значений IEEE 754:

0.1 => 0:01111111011:1001100110011001100110011001100110011001100110011010
0.2 => 0:01111111100:1001100110011001100110011001100110011001100110011010

Обратите внимание, что мантисса состоит из повторяющихся цифр 0011, Это ключ почему в вычислениях есть ошибки — 0,1, 0,2 и 0,3 не могут быть представлены в двоичном виде точно в конечный количество двоичных разрядов больше 1/9, 1/3 или 1/7 может быть точно представлено в десятичные цифры.

Преобразование показателей степени в десятичное, удаление смещения и повторное добавление подразумеваемых 1 (в квадратных скобках) 0,1 и 0,2:

0.1 = 2^-4 * [1].1001100110011001100110011001100110011001100110011010
0.2 = 2^-3 * [1].1001100110011001100110011001100110011001100110011010

Чтобы сложить два числа, показатель должен быть одинаковым, т.е.

0.1 = 2^-3 *  0.1100110011001100110011001100110011001100110011001101(0)
0.2 = 2^-3 *  1.1001100110011001100110011001100110011001100110011010
sum = 2^-3 * 10.0110011001100110011001100110011001100110011001100111

Поскольку сумма не имеет формы 2^N * 1. {bbb} увеличиваем показатель на единицу и сдвигаем десятичную (двоичный) укажите, чтобы получить:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)

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

a = 2^-2 * 1.0011001100110011001100110011001100110011001100110011
x = 2^-2 * 1.0011001100110011001100110011001100110011001100110011(1)
b = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

Обратите внимание, что а также б отличаются только последним битом; ...0011 + 1 знак равно ...0100, В этом случае значение с наименьшим значащим нулевым битом б, итого сумма:

sum = 2^-2 * 1.0011001100110011001100110011001100110011001100110100

TL; DR

Пишу 0.1 + 0.2 в двоичном представлении IEEE 754 (с двоеточиями, разделяющими три части) и сравнивая его с 0.3, это (я поставил отдельные биты в квадратных скобках):

0.1 + 0.2 => 0:01111111101:0011001100110011001100110011001100110011001100110[100]
0.3       => 0:01111111101:0011001100110011001100110011001100110011001100110[011]

Преобразованные обратно в десятичные, эти значения:

0.1 + 0.2 => 0.300000000000000044408920985006...
0.3       => 0.299999999999999988897769753748...

Разница ровно 2^-54, что составляет ~ 5,5511151231258 × 10^-17 — незначительный (для многих приложений) по сравнению с исходными значениями.

Сравнение последних нескольких битов числа с плавающей запятой по своей природе опасно, так как любой, кто читает знаменитые «Что каждый компьютерщик должен знать об арифметике с плавающей точкой«(который охватывает все основные части этого ответа) будет знать.

Большинство калькуляторов используют дополнительные защитные цифры чтобы обойти эту проблему, которая как 0.1 + 0.2 даст 0.3: последние несколько бит округлены.

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

Если компьютер работал в базе 10, 0.1 было бы 1 x 10⁻¹, 0.2 было бы 2 x 10⁻¹, а также 0.3 было бы 3 x 10⁻¹, Целочисленная математика проста и точна, поэтому добавление 0.1 + 0.2 очевидно, приведет к 0.3,

Компьютеры обычно не работают в базе 10, они работают в базе 2. Вы можете получить точные результаты для некоторых значений, например 0.5 является 1 x 2⁻¹ а также 0.25 является 1 x 2⁻²и добавление их приводит к 3 x 2⁻², или же 0.75, Именно так.

Проблема возникает с числами, которые могут быть представлены точно в базе 10, но не в базе 2. Эти числа должны быть округлены до их ближайшего эквивалента. Предполагая, что очень распространенный IEEE 64-битный формат с плавающей запятой, ближайший номер к 0.1 является 3602879701896397 x 2⁻⁵⁵и ближайший номер к 0.2 является 7205759403792794 x 2⁻⁵⁵; сложение их вместе приводит к 10808639105689191 x 2⁻⁵⁵или точное десятичное значение 0.3000000000000000444089209850062616169452667236328125, Числа с плавающей точкой обычно округляются для отображения.