Машинная арифметика и идиомы численного программирования

Машинная арифметика и идиомы численного программирования

Научно-технические расчеты - простейшее применение вычислительной техники.

Эдсгер Дейкстра

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

Представление вещественных чисел

В большинстве современных компьютеров аппаратно реализована вещественная арифметика, соответствующая стандарту IEEE. В соответствии со стандартом существует 2 основных представления вещественного числа - с одинарной (float) и двойной (double) точностью. Во всех представлениях один бит используется как знаковый. Есть еще одно представление вещественных чисел - 10-байтовое, используемое при вычислениях для хранения промежуточных результатов и называемое представлением с расширенной точностью.

тип	длина	мантисса	показатель
float	4 байта	23 бита	8 битов
double	8 байтов	52 бита	11 битов

Машинное представление вещественного числа с плавающей точкой имеет следующий вид: (+/-)M * 2^E, где M - вещественная мантисса, E - целочисленный показатель. Мантисса представлена в виде последовательности разрядов двоичной дроби:

М = М₀ + М₁/2 + М₂/4 + ... + М_n/2ⁿ

Для представления всех вещественных чисел кроме нуля используется нормализованная форма, когда нулевой разряд мантиссы М₀ равен 1. При таком представлении нулевой разряд опускается и хранятся только разряды М₁…М_n. Таким образом, мантисса M удовлетворяет неравенству i <= M < 2.

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

Простые примеры

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

float x4 = 0.1;

double x8 = 0.1;

не стоит надеяться, что x4 == 0.1 или х8 == 0.1. Дело в том, что при сравнении используется 10-байтовое представление для константы 0.1, не совпадающее с 8-байтовым в случае переменной х8 и 4-байтовым для х4. Ясно, что по аналогичной причине не будет выполнено равенство х4 == х8.

Последовательные операции с непредставимыми числами могут приводить к накоплению погрешности. Например, если просуммировать 1000 4-байтовых представлений (float) числа 0.1, то мы получим результат, отличающийся на 0.000953674 от точного. Это - вполне заметная погрешность.

Просуммируем вещественные числа вида 1.0/j при j = 1... 1000 в разном порядке - по возрастанию и по убыванию. При использовании вещественной арифметики однократной точности (float) полученные результаты будут отличаться на 6.67572е-006.

Первые выводы

При работе с вещественными числами на точное равенство надеяться не стоит даже при проведении простейших вычислений.

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

В машинной вещественной арифметике нарушаются даже простейшие свойства чисел (например коммутативность сложения), на которые мы привыкли надеяться.

Модельная арифметика

Для построения примеров удобно использовать следующую модельную арифметику. Пусть наш воображаемый компьютер использует десятичную систему счисления, причем мантисса имеет 4 десятичных разряда, а показатель - 2 десятичных разряда. Вот одно из вещественных чисел, представимых в такой арифметике: 9.876*10^-12. Ясно, что таких вещественных чисел имеется лишь конечное число, причем в нашей арифметике есть минимальное и максимальное числа:

min = -9.999 * 10^99,

max = 9.999 * 10^99.

Есть также минимальное положительное число:

min₊ = 1.000 * 10^-99.

Потеря значимости

Рассмотрим в описанной выше модельной арифметике операцию сложения чисел 1.234 *