- А мне КОМПЬЮТЕР так посчитал!
На лице у девушки-оператора написано убеждённое превосходство над озадаченной старушкой, переводящей взгляд от жировки с квартплатой на девушку и обратно. Знакомая ситуация?
Может быть, девушке и удалось убедить пенсионерку. Но нас-то не проведёшь! Мы-то знаем цену таким словам. Кто-то знаком со списком признанных ошибок реализации современных микропроцессоров, кто-то сам разрабатывает программы для операторов и врядли стал бы защищать их с той же самоотверженностью, что их пользователь.
Однако в этой статье мне хотелось бы обсудить только один аспект многогранной проблемы правильности компьютерных вычислений, а именно -- вопрос точности представления десятичных данных.
Никому не нужно доказывать, что арифметико-логические устройства современных процессоров архитектуры Intel (на которых построено большинство серверов и рабочих станций) обрабатывают данные, представленные в двоичной системе счисления. Для восприятия же человеком числовые данные должны быть представлены в десятичной системе счисления. Это тоже не нужно доказывать.
В памяти компьютера числа хранятся в двоичном представлении: для него отводятся ячейки памяти, способные хранить W двоичных разрядов, где W - размер машинного слова. С одной стороны, интерпретация конкретного состояния машинного слова предоставляется фантазии программиста. С другой стороны, есть устоявшиеся традиции представления числовых данных, для которых имеется аппаратная поддержка в виде операций на уровне команд микропроцессора (или математического сопроцессора). И которыми было бы глупо не воспользоваться (хотя дальше мы увидим, что не так уж и глупо). Так, целые числа записываются, как правило, в дополнительном коде. А вещественные числа -- в формате c плавающей точкой в соответствии со стандартом IEEE 754. В любом случае, точность представления числа ограничена конечной величиной W разрядной сетки. Отметим, что стандартные типы данных (Integer, Double) таких языков как Паскаль, Си и Си++ являются отображениями именно таких традиционных чисел.
Величину числа, записанного в системе счисления с основанием b в виде последовательности цифр an-1...a2a1a0,a-1a-2...a-(m-1)a-m, можно перевести в десятичную систему счисления следующим образом:
vdec = a(n-1)*b(n-1) + ... + a2 * b 2 + a1 * b + a0 + a-1/b + a-2/b2 + ... + a-(m-1)/b(m-1) + a-m/bm
А все ли помнят, как записать десятичное число в двоичной системе счисления? Если нам нужо перевести десятичную дробь в другую систему счисления, то придётся отдельно переводить целую часть, и отдельно -- дробную. Перевод целой части обычно осуществляют так называемым методом деления, в ходе которого выписывают остатки от последовательного её деления на величину основания b. По завершении процесса записанные остатки читают в обратном порядке, начиная с последнего. Дробную часть переводят методом умножения, для чего её умножают на величину b. Целая часть результата представляет собой первую цифру после запятой в искомой дроби. Дробная часть результата снова умножается на b, и так далее. (*)
Давайте для наглядности продемонстрируем этот процесс на каком-нибудь примере. Ну, хотя бы, на числе 10.625dec, которое переведём в двоичную систему счисления.
Итак, разбираем целую часть:
10 : 2 = 5 (остаток 0);
5 : 2 = 2 (остаток 1);
2 : 2 = 1 (остаток 0);
1 : 2 = 0 (остаток 1).
Значит, 10dec = 1010bin.
А теперь -- дробь:
0.625 * 2 = 1.25 (целая часть 1)
0.25 * 2 = 0.5 (целая часть 0)
0.5 * 2 = 1.0 (целая часть 1).
Получилось, что 0.625dec = 0.101bin. То есть 10.625dec = 1010.101bin
Красота! А теперь давайте переставим местами дробную и целую часть в исходном числе и повторим процедуру для числа 625.10dec.. Целую часть преобразовывать довольно нудно, поэтому предлагаю проверить, что 625dec. = 1001110001bin. Ну, а дробная часть небольшая, поэтому снова будем протоколировать:
0.1 * 2 = 0.2 (целая часть 0)
0.2 * 2 = 0.4 (целая часть 0)
0.4 * 2 = 0.8 (целая часть 0)
0.8 * 2 = 1.6 (целая часть 1)
0.6 * 2 = 1.2 (целая часть 1)
0.2 * 2 = 0.4 (целая часть 0)
Стоп! Кажется, это уже было! Сейчас будем умножать 0.4 на 2, а ещё через две операции снова вернёмся к 0.2. И этот процесс никогда не закончится, мы получим бесконечную периодическую двоичную дробь 0.0(0011)bin!
Что же получается? А вот что: любое заданное натуральное число можно точно записать в конечном числе двоичных разрядов. Однако далеко не любую конечную десятичную дробь можно представить в виде конечной двоичной дроби.И этот факт сам по себе достаточно прискорбный. Потому что мы ещё не начали никаких вычислений, чтобы говорить об ошибках округления, а уже имеем ошибку представления! И не важно, сколько разрядов мы будем отводить для записи числа, важно то, что мы никогда не сможем выделить ему бесконечное число разрядов, а значит, ошибка представления будет иметь место в любом случае.
Вероятно, на это не стоило бы обращать большого внимания, если бы над числами в дальнейшем не выполнялись операции. А они выполняются. И зачастую в циклах. Поэтому самые незначительные ошибки растут со стремительностью снежного кома в подходящую погоду.
Конечно, сказанное выше не может являться поводом для паники. Однако задуматься над этим стоит. Особенно тем, кто связан с вычислениями финансового характера. И проявлять осторожность нужно буквально с первых шагов в разработке программы, то есть с выбора типов данных для хранения числовых величин. Если кто-то ещё сомневается, что вопрос актуален, предлагаю ознакомиться с дополнительными материалами, например, приведенными в статьях IEEE 754 - стандарт двоичной арифметики с плавающей точкой" и "DECFLOAT - тип данных будущего".
Какой выход видится из этой непростой ситуации? Первый -- фантастический, но радикальный. Необходимо ввести в хозяйственное обращение систему счисления с основанием b = n2, например, восьмеричную. Помимо прямой выгоды от точного представления всех восьмеричных дробей в двоичной записи получим благодарность потомков за упрощение таблицы умножения, экономии на материалах для кнопок калькуляторов, банкоматов, телефонов и других клавиатур.
Второй -- реалистичный. В разумных пределах отказаться от использования традиционных типов данных, а использовать в вычислениях десятичную арифметику. Вариантов здесь много, от реализации "школьных" алгоритмов для десятичных дробей до применения простых дробей. Ведь 625.10 = 625 целых 10 сотых, т. е. 625 + 10 / 100, где числа 10 и 100 в числителе и знаменателе дроби -- целые, а значит точно представимы двоичной системе счисления. Заинтересовавшимся предлагаю вспомнить университетский курс компьютерной алгебры, чтобы построить действительно эффективные и правильные алгоритмы.
P.S. Кто-нибудь ещё сомневается, что программисту нужны знания в области математики?
(*) ЭВМ и микропроцессор. Бильдюкевич Е. В., Гурачевский В. Л., Шушкевич С. С. - Мн.: Нар. асвета, 1990
Релоцировались? Теперь вы можете комментировать без верификации аккаунта.