• От арифметики компьютерной к арифметике школьной.

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

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

    Так в чем же отличие компьютерной арифметики от арифметики классической? А отличие состоит в том, что в компьютере десятичные вычисления выполняются в двоичной арифметике.  Десятичную арифметику в BCD-кодах мы здесь не рассматриваем. При этом на входе вычислительного устройства  входные   данные  задаются в десятичном виде с определенной  заданной точностью (количеством значащих цифр) и результат вычислений мы тоже оцениваем в десятичном виде. Все вычисления в компьютере выполняются не над десятичными числами, а над их двоичными представлениями. Причем точность двоичного представления определяется количеством разрядов операционных регистров компьютера.

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

    В целочисленной арифметике двоичные и десятичные числа взаимно-однозначны. Когда же идет речь о числах с дробной составляющей, т.е. о вещественных числах, то все становится гораздо хуже. При вычислении в одном конкретном базисе (системе счисления) , если мы пользуемся правилами приближенных вычислений, мы получаем правильный результат, как для десятичных, так и для двоичных дробных чисел.  Например,  в десятичной арифметике – 0.12+ 0.121 ≈ 0.24, в двоичной – 0.101+0.1=1.001≈1.01. И это правильные результаты.

    Если же нам надо  вычислить, например,  сумму 0.12+ 0.1 в десятично-двоичной арифметике, то мы должны представить эти десятичные числа в двоичном виде – 0.12 = 0.000111101011…, 0.1 = 0.000110011001… . Каждое двоичное представление наших десятичных чисел имеет бесконечное число цифр и поэтому  точной десятичной суммы мы никогда не получим, сколько бы двоичных цифр  мы ни брали. Так, вычисленная по правилам двоичной арифметики,  сумма восьмиразрядных двоичных представлений наших десятичных чисел  даст 0.00011110110 + 0.000110011010= 0.00111000011. В результате округления двоичного значения суммы до 8 значащих цифр мы получим число 0.0011100010, которое равно десятичному числу 0.220703125. Это число является представимым и оно является ближайшим числом, к которому было округлено двоичное число   0.00111000011.

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

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

    Например, в результате десятично-двоичных вычислений мы получили двоичное число 0.000101101101, в котором 9 значащих цифр. Это число равно десятичному числу 0.089111328125. Если у нас 8-разрядный компьютер, то наше двоичное число должно быть округлено до числа 0.00010110111, которое равно  представимому десятичному числу 0.08935546875. Но нас интересуют десятичные вычисления  с некоторой заданной десятичной точностью, которая может не совпадать с точностью представимого числа. Под точностью, как всегда, мы подразумеваем количество значащих цифр, которым представлено число. Поэтому десятичные числа, представленные в двоичном виде, должны округляться до ближайшего двоичного представления десятичного числа с заданным  числом десятичных значащих цифр. Например, если десятичные расчеты ведутся в двоичном виде с точностью  до 2 значащих десятичных цифр, то правильным округлением  двоичных чисел 0.0011100000=0.21875 и 0.0011100010 =0.220703125 должно  дать округленное  число  0.22 = 0.0011100001= 0.2197265625. Это двоичное число 0.0011100001 является наиболее близким  к правильно округленному десятичному числу  0.22, и для заданной точности двоичного представления (у нас это 8) оно уникально.

    Если обозначить через ◦[…] операцию округления, то ◦[0.0011100000]=◦[ 0.0011100010]= 0.0011100001. Следовательно ◦[0.0011100000] — ◦[0.0011100010] = 0. Таким образом,  разность правильно округленных двоичных чисел дает строгий нуль. Следовательно, сравнение на равенство двух правильно округленных чисел  становится  тривиальной задачей. Упрощается также решение и ряда других задач, сложность которых обусловлена концепцией аппроксимации десятичных чисел двоичными кодами принятой в стандарте IEEE754. Суть этой концепции в том, что точность аппроксимации десятичных чисел определена количеством разрядов мантиссы двоичного числа, которое аппроксимирует заданное десятичное число.

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

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

     

  • Десятично-двоичная арифметика

    В своих статьях мы все время говорим о десятично-двоичных вычислениях. При этом мы имеем в виду, что на входе и выходе вычислительного устройства числа представлены в привычном для нас десятичном виде. Например, как в популярном приложении Excel. Причем, в самом устройстве все вычисления выполняются в двоичном коде. Мы не будем рассматривать здесь десятичную арифметику, которая эмулируется в вычислительном устройстве BCD кодами, так как такая арифметика выполняет десятичные вычисления над десятичными числами. Остановимся на двоичной аппроксимации десятичных вычислений.

  • Катастрофическая отмена.

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

  • Десятичное сравнение двоичных чисел

    Смысл любых математических вычислений – ответить на вопросы: равно ли  одно число другому и если не равно, то на сколько, или во сколько раз они отличаются друг от друга. Ответить на вопрос, какое из чисел больше или меньше не составляет труда, если есть ответ на вопрос, равны или нет сравниваемые числа. А ответить на вопрос о равенстве чисел не очень просто в рамках двоичной  компьютерной арифметики.

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

  • Погрешность измерения и погрешность преобразования в десятично-двоичной арифметике

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

    Числа, с которыми пользователь имеет дело, разделим на два класса — числа, полученные в результате вычислений, и числа, полученные в результате измерений.

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

    Точные числа, это множество натуральных чисел и числа, полученные в результате арифметических операций над натуральными числами. Причем, в результате арифметических операций над натуральными числами, могут быть получены как рациональные, так и иррациональные числа. И те и другие множества чисел могут представляться в виде десятичных  чисел с бесконечным количеством цифр в их дробной части. Например, рациональное число 1/3=0.333… имеет бесконечное число цифр, каждое из которых равно 3. Иррациональное десятичное число √2 =1.414… также состоит из бесконечного числа цифр. Оба этих множества объединяет то, что при желании мы можем точно вычислить  любую цифру в дробной части  этих чисел.

  • Что такое ulps и что такое ulp?

    Для решения проблемы сравнения двух близких чисел  был придуман термин ulp.  Аббревиатуру ulp впервые ввел известный ученый в области вычислительной математики  У.Кэхэн [1]. Обозначение ulp (Unit in the Last Place) является английским сокращением «единицы на последнем месте». С тех пор этот термин широко используется в компьютерной литературе, а также применяется в ряде языков программирования. Но, что интересно, единой интерпретации этого термина в настоящее время не существует. В [2] собраны и рассматриваются основные определения термина ulp.  Некоторые из них даны в работах  У.Кэхэна [1], Д.Харрисона [4] и Д.Голдберг [5]. Ниже мы приведем свою интерпретацию этого понятия, которое не противоречит определению Д.Голдберга и при этом, как нам кажется, оказывается простым и логичным. 

  • КОЕ-ЧТО ОБ ОТНОШЕНИЯХ ЧИСЕЛ ДЕСЯТИЧНЫХ И ЧИСЕЛ ДВОИЧНЫХ

                Двоичная + десятичная ≠ любовь

     

    Привычная для пользователя арифметика, это десятичная арифметика.

    Существуют также b-ичные арифметики, где b- база системы счисления отличная от 10, принимающая любое ненулевое значение [1].

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

    Если экспонента числа фиксирована и мантисса числа является целым числом, то такой формат называется форматом с фиксированной точкой.  Частным случаем формата с фиксированной точкой является целое число, в котором экспонента равна нулю. Такой формат является форматом целого числа.