Источник: http://introcs.cs.princeton.edu/java/91float/
Перевод статьи Robert Sedgewick and Kevin Wayne – Floating Point. October 19,2008.
Отличительной чертой, отделяющей традиционные компьютерные науки от научных вычислений является использование дискретной математики (0 и 1), а не непрерывной математики и математического анализа. Переход от целых, вещественных чисел больше, чем косметические изменения. Цифровые компьютеры не могут представлять все действительные чисел точно, поэтому мы сталкиваемся с новыми проблемами при разработке компьютерных алгоритмов для вещественных чисел. Теперь, в дополнение к анализу времени выполнения и памяти, мы должны иметь дело с «правильностью» решения. Это сложная проблема еще более усугубляется, так как многие важные научные алгоритмы необходимо модифицировать для размещения в дискретных компьютерах. Так же, мы обнаружили, что некоторые дискретные алгоритмы изначально слишком медленные (по сравнению с экспоненциальным полином), мы увидели, что некоторые алгоритмы с плавающей запятой слишком неточные (стабильные по сравнению с неустойчивыми). Иногда эта проблема может быть исправлена путем разработки более умных алгоритмов. С плавающей точкой возникают проблемы, которые могут быть присущи (плохое кондиционирование), например, точный долгосрочный прогноз погоды. Чтобы иметь эффективные вычислительные системы, мы должны уметь классифицировать наши алгоритмы и проблемы соответственно.
Некоторые из величайших достижений 20-го века не были бы возможными без цифровых компьютеров с плавающей запятой. Тем не менее, эту тему не очень хорошо понимает большинство программистов и она является постоянным источником путаницы. В феврале 1998 года выступление озаглавленное, как «расширение Java для численных вычислений» Джеймс Гослинг утверждает, "95% людей там совершенно невежественно относятся к плавающей запятой". Тем не менее, основные идеи, лежащие в плавающей запятой не трудные, и мы будем прояснять путаницу, которой страдает большинство новичков.
Сначала мы опишем, как числа с плавающей запятой представлены. Java использует подмножество двоичных IEEE 754-стандартов с плавающей запятой для представления чисел с плавающей запятой и определяет результаты арифметических операций. Практически все современные компьютеры соответствуют этому стандарту. Он представлен с использованием 32 бит, и каждой возможной комбинации битов представляет собой одно вещественное число. Это означает, что в большинстве 232 возможных вещественных чисел можно точно представить, даже если существует бесконечное множество действительных чисел (даже между 0 и 1). IEEE стандарт использует внутреннее представление похоже на научные обозначения, но в двоичной системе, а не в десятичной. Это покрывает диапазон от ± 1.40129846432481707e-45 ± 3.40282346638528860e+38. с 6 или 7 значащих десятичных знаков, в том числе, плюс бесконечность, минус бесконечность и NaN (не число). Число содержит знаковый бит S (интерпретируется как плюс или минус), 8 бит для экспоненты E и 23 бита для мантиссы М. десятичное число представлено в соответствии со следующей формулой.
(-1)s × m × 2(e – 127
• Знаковый бит S (бит 31). Самый старший бит представляет знак числа (1 для отрицательного, 0 для положительного).
• Экспонента Е (биты 30 - 23). Следующие 8 бит представляют экспоненту. По соглашению показатель смещается на 127. Это означает, что для представления двоичного показателя 5, мы кодируем 127 + 5 = 132 в двоичной системе (10000100). Для представления двоичныхпоказателем -5 мы кодирования 127 - 5 = 122 в двоичной (01111010). Это соглашение является альтернативным дополнением до двух обозначений для представления отрицательных чисел.
• Мантисса М (биты 22 - 0). Оставшиеся 23 бита представляют собой нормированную мантиссу, от 0,5 до 1. Это нормализация всегда возможна, регулируя бинарный показатель соответственно. Двоичные фракции работают как десятичная дробь: 0,1101 представляет собой 1/2+1/4+1/16 =13/16 = 0,825. Не каждое десятичное число может быть представлено в виде двоичной дроби. Например, 1/10 = 1/16+1/32+1/256+1/512+1/4096+1/8192... В этом случае число 0.1 аппроксимируется ближайшими 23 битами двоичной дроби 0,000110011001100110011 ... Работает еще одна оптимизация: Поскольку мантисса всегда начинается с 1, нет необходимости ее явно хранить.
В качестве примера десятичное число 0,085 хранится в виде:
00111101101011100001010001111011.
0.085:
bits: 31 30-23 22-0
binary: 0 01111011 01011100001010001111011
decimal: 0 123 3019899
Это как раз представляет собой число 2e-127 (1 + m / 223) = 2-4(1 + 3019899/8388608) = 11408507/134217728 = 0.085000000894069671630859375.
Double похож на Float кроме того, что его внутреннее представление использует 64 бит, 11 бит экспоненты со сдвигом в 1023, и 52 бит мантиссы.Это покрывает диапазон от ± 4.94065645841246544E-324 до ±1.79769313486231570E+308 с 14 или 15 значащих цифр точности....
Точность = герметичность спецификации. Правильность не следует путать точность с точностью. 3,133333333 является оценка математическая константа ?, которая указана на 10 десятичных цифр точности, но это только два десятичных цифр точности. Как сказал Джон фон Нейман однажды сказал: "Там нет смысла в той, точности, когда вы даже не знаете, что вы говорите." Java обычно выводит числа с плавающей запятой с 16 или 17 десятичными цифрами точности, но не следует слепо верить, что это означает, что там много цифр точности! Калькуляторы обычно отображают 10 цифр, но вычисляют с 13 цифрами. Каган: зеркало для космического телескопа Хаббла было создано с большой точностью, но с неправильной спецификацией. Таким образом, он изначально имел большой провал, поскольку он не может производить изображения с высоким разрешением, как ожидалось. Тем не менее, это точно включено астронавтам удалось установить корректирующие линзы для уравновешивания ошибок. Валютные расчеты часто определяется с точки зрения точности, например, обменный курс евро должен быть заключен до 6 цифр.
Программирование с плавающей точкой может быть непонятным и опасным процессом для непосвященного. Арифметика целых чисел является точной, если ответ на этот вопрос не выходит за пределы диапазона целых чисел, которые могут быть представлены (переполнение). В отличие от арифметики с плавающей запятой, которая не является точной, поскольку некоторые вещественные числа требует бесконечного числа цифр, например, математические константы и электронное π и 1/3. Однако, большинство начинающих Java-программистов с удивлением узнают, что 1/10 точно не представима ни в стандартных двоичных чисел с плавающей точкой. Эти ошибки округления могут распространяться в расчет не-интуитивным образом.
• Округление десятичных дробей. Например, в первом фрагменте кода ниже от FloatingPoint.java выдает «ложь», а второй «истина».
double x1 = 0.3;
double x2 = 0.1 + 0.1 + 0.1;
StdOut.println(x1 == x2);
double z1 = 0.5;
double z2 = 0.1 + 0.1 + 0.1 + 0.1 + 0.1;
StdOut.println(z1 == z2);
• Метод Ньютона. Более реалистичный пример следующий фрагмент кода целью которого является вычисление квадратного корня с путем итерации метода Ньютона. Математически, последовательность итераций сходится к √c сверху, так что t2 - c > 0. Тем не менее, число с плавающей запятой имеет только конечное число бит точность, поэтому, в конце концов, мы можем ожидать, t2 равного с точно, до машинной точности.
double EPSILON = 0.0;
double t = c;
while (t*t - c > EPSILON)
t = (c/t + t) / 2.0;
Действительно, для некоторых значений с, метод работает.
% java Sqrt 2 % java Sqrt 4 % java Sqrt 10
1.414213562373095 2.0 3.162277660168379
Это может дать нам уверенность, что наш фрагмент является правильным. Но удивительная вещь происходит, когда мы пытаемся вычислить квадратный корень из 20. Наша программа застревает в бесконечном цикле! Этот тип ошибки называется ошибкой округления. Машина точности наименьшее число ε такое, что (1.0 + ε ! = ε). В Java, это XYZ с double XYZ с float. Переменная ε, ошибка, допуск к небольшому положительному значению помогает, но не решает проблему (см. упражнение XYZ).
Мы должны быть довольны приближением квадратного корня. Надежным способом расчета является выбор некоторых ошибок ε, с точностью 1E-15, нахождение значения t такого, что: |t - c/t | < ε t. Мы используем относительную погрешность вместо абсолютной погрешности, в противном случае программа может войти в бесконечный цикл (см. упражнение XYZ).
double epsilon = 1e-15;
double t = c;
while (Math.abs(t*t - c) > c*epsilon)
t = (c/t + t) / 2.0;
• Гармоническая сумма. Возможно мотивировать, пытаясь оценить γ = limit Эйлера при n стремящимся к бесконечности в γn = Hn - ln n. Предел существует и составляет около 0,5772156649. Удивительно, но даже не известно, является ли γ иррациональным.
Программа вычисления гармонической суммы HarmonicSum.java 1/1 + 1/2 + ... + 1 / N использует одинарную точность и двойную точность. С одинарной точностью, когда N = 10000, сумма находиться с точностью до 5 десятичных цифр, при N = 1000000 это с точностью до всего лишь 3 десятичных цифр, при N = 10000000 это точно только 2 десятичных цифр. В самом деле, когда N достигает 10 млн., сумма никогда не увеличивается. Несмотря на то, гармоническое расхождение суммы до бесконечности, для чисел с плавающей запятой сходится к конечному числу! Это опровергает распространенное заблуждение, что если вы решаете проблему, которая требует только 4 или 5 десятичных цифр точности, то вы для безопасности используете такой тип, который хранит 7. Многие численные расчеты (например, интеграция или решения дифференциальных уравнений) привлекают подведение много малых условия. Ошибки могут накапливаться. Это накопление ошибок округления может привести к серьезным проблемам.
Лучше видно по формуле: : γ ≈ γn - 1/(2n) + 1/(12n2). С точностью до 12 десятичных знаков для n = 1 000 000.
Каждый раз, когда вы выполняете арифметические операции, вы представляете дополнительную погрешность, по крайней мере ε. Керниган и Plauger: "числа с плавающей точкой, как груды песка, каждый раз, когда вы перемещаете тот, который вы теряете немного песка и забрать немного грязи». Если ошибки возникают случайным образом, мы можем ожидать кумулятивного ошибки sqrt(N) εm. Тем не менее, если мы не будем бдительны при проектировании наших численных алгоритмов, эти ошибки могут распространяться в очень неблагоприятных и не интуитивно-понятных путях, что ведет к кумулятивным ошибки N εm или хуже.