С точностью до бита, или почему компьютеры всегда ошибаются.

- А мне КОМПЬЮТЕР так посчитал! На лице у девушки-оператора написано убеждённое превосходство над озадаченной старушкой, переводящей взгляд от жировки с квартплатой на девушку и обратно. Знакомая ситуация? Может быть, девушке и удалось убедить пенсионерку. Но нас-то не проведёшь! Мы-то знаем цену таким словам. Кто-то знаком со списком признанных ошибок реализации современных микропроцессоров, кто-то сам разрабатывает программы для операторов и врядли стал бы защищать их с той же самоотверженностью, что их пользователь. Однако в этой статье мне хотелось бы обсудить только один аспект многогранной проблемы правильности компьютерных вычислений, а именно -- вопрос точности представления десятичных данных. Никому не нужно доказывать, что арифметико-логические устройства современных процессоров архитектуры Intel (на которых построено большинство серверов и рабочих станций) обрабатывают данные, представленные в двоичной системе счисления. Для восприятия же человеком числовые данные должны быть представлены в десятичной системе счисления. Это тоже не нужно доказывать. В памяти компьютера числа хранятся в двоичном представлении: для него отводятся ячейки памяти, способные хранить W двоичных разрядов, где W - размер машинного слова. С одной стороны, интерпретация конкретного состояния машинного слова предоставляется фантазии программиста. С другой стороны, есть устоявшиеся традиции представления числовых данных, для которых имеется аппаратная поддержка в виде операций на уровне команд микропроцессора (или математического сопроцессора). И которыми было бы глупо не воспользоваться (хотя дальше мы увидим, что не так уж и глупо). Так, целые числа записываются, как правило, в дополнительном коде. А вещественные числа -- в формате c плавающей точкой в соответствии со стандартом IEEE 754. В любом случае, точность представления числа ограничена конечной величиной W разрядной сетки. Отметим, что стандартные типы данных (Integer, Double) таких языков как Паскаль, Си и Си++ являются отображениями именно таких традиционных чисел. Величину числа, записанного в системе счисления с основанием b в виде последовательности цифр a_n-1...a₂a₁a₀,a_-1a_-2...a_-(m-1)a_-m, можно перевести в десятичную систему счисления следующим образом: v_dec = a_(n-1)*b^(n-1) + ... + a₂ * b ² + a₁ * b + a₀ + a_-1/b + a_-2/b² + ... + a_-(m-1)/b^(m-1) + a_-m/b^m А все ли помнят, как записать десятичное число в двоичной системе счисления? Если нам нужо перевести десятичную дробь в другую систему счисления, то придётся отдельно переводить целую часть, и отдельно -- дробную. Перевод целой части обычно осуществляют так называемым методом деления, в ходе которого выписывают остатки от последовательного её деления на величину основания b. По завершении процесса записанные остатки читают в обратном порядке, начиная с последнего. Дробную часть переводят методом умножения, для чего её умножают на величину b. Целая часть результата представляет собой первую цифру после запятой в искомой дроби. Дробная часть результата снова умножается на b, и так далее. ^(*) Давайте для наглядности продемонстрируем этот процесс на каком-нибудь примере. Ну, хотя бы, на числе 10.625_dec, которое переведём в двоичную систему счисления. Итак, разбираем целую часть: 10 : 2 = 5 (остаток 0); 5 : 2 = 2 (остаток 1); 2 : 2 = 1 (остаток 0); 1 : 2 = 0 (остаток 1). Значит, 10_dec = 1010_bin. А теперь -- дробь: 0.625 * 2 = 1.25 (целая часть 1) 0.25 * 2 = 0.5 (целая часть 0) 0.5 * 2 = 1.0 (целая часть 1). Получилось, что 0.625_dec = 0.101_bin. То есть 10.625_dec = 1010.101_bin Красота! А теперь давайте переставим местами дробную и целую часть в исходном числе и повторим процедуру для числа 625.10_dec.. Целую часть преобразовывать довольно нудно, поэтому предлагаю проверить, что 625_dec. = 1001110001_bin. Ну, а дробная часть небольшая, поэтому снова будем протоколировать: 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 = n², например, восьмеричную. Помимо прямой выгоды от точного представления всех восьмеричных дробей в двоичной записи получим благодарность потомков за упрощение таблицы умножения, экономии на материалах для кнопок калькуляторов, банкоматов, телефонов и других клавиатур. Второй -- реалистичный. В разумных пределах отказаться от использования традиционных типов данных, а использовать в вычислениях десятичную арифметику. Вариантов здесь много, от реализации "школьных" алгоритмов для десятичных дробей до применения простых дробей. Ведь 625.10 = 625 целых 10 сотых, т. е. 625 + 10 / 100, где числа 10 и 100 в числителе и знаменателе дроби -- целые, а значит точно представимы двоичной системе счисления. Заинтересовавшимся предлагаю вспомнить университетский курс компьютерной алгебры, чтобы построить действительно эффективные и правильные алгоритмы. P.S. Кто-нибудь ещё сомневается, что программисту нужны знания в области математики? ^(*) ЭВМ и микропроцессор. Бильдюкевич Е. В., Гурачевский В. Л., Шушкевич С. С. - Мн.: Нар. асвета, 1990

16 лет dev.by — «дефолтный» источник информации о беларусском ИТ

Вы можете...