Продолжая исследовать проблему точности десятичных вычислений средствами двоичной арифметики, начатую в предыдущих постах [1,2,3,4], мне удалось разработать алгоритмы вычисления вещественных чисел, представленных в формате десятичных чисел с плавающей точкой, которые дают такой же точный результат, как если бы вычисления велись вручную.
В этих алгоритмах использована двоичная арифметика, регламентированная стандартом IEEE754. Для проверки работы алгоритмов была разработана тестовая программа на C++, реализующая 18-ти разрядный десятичный калькулятор.
Поскольку объем материала превышает формат поста, я изложил основные моменты в виде тезисов. Назовем этот пост «Майскими тезисами»:(.
Итак.
Привычная для пользователя арифметика, это десятичная арифметика.
Существуют также b-ичные арифметики, где b- база системы счисления, принимающая любое ненулевое значение [5].
Для отображения чисел в разных масштабах используется запись чисел с плавающей точкой в виде произведения мантиссы и некоторой произвольной степени базы. Это, так называемая, экспоненциальная запись.
Если степень числа фиксирована и мантисса числа является целым числом, то такой формат называется форматом с фиксированной точкой. Частным случаем формата с фиксированной точкой является число, в котором степень равна нулю. Такой формат является форматом целого числа.
Если мантисса представляет собой дробное число в b-ичной системе счисления с целой частью c≠0 и c < b, то такое число называется нормализованным.
Несмотря на то, что по своей физической природе числа являются приближенными, для вычислительного устройства это точные числа и операции над ними устройство должно производить с заданной пользователем точностью.
Под точными вычислениями в арифметике подразумевают получение результата с заданным количеством верных значащих цифр после точки [6].
Все вычисления в компьютере производятся в двоичном виде. Для них база b = 2.
Поскольку двоичная и десятичная системы счисления несоизмеримы, то при конвертации десятичных вещественных чисел в двоичный код чаще всего мы получаем приближенное значение двоичного эквивалента десятичного числа. Поэтому, при переводе десятичных чисел в двоичные возникают погрешности представления.
Десятичные числа, которые имеют точный двоичный эквивалент, называют представимыми.
Десятичные числа, которые не имеют точного двоичного эквивалента, называются непредставимыми.
Все целые десятичные числа представимы, если количество значащих цифр в их двоичном эквиваленте не превышает разрядную сетку области машинного слова, в которую они записываются.
Чем большим количеством двоичных разрядов представлен десятичный эквивалент числа в двоичном виде, тем меньше ошибка представления. Этим объясняется стремление постоянно наращивать разрядность операционного регистра процессора.
Любое десятичное число, двоичный эквивалент которого содержит количество значащих цифр, превышающее разрядную сетку машинного слова, может быть представлено только приближенно.
Арифметические действия, в результате которых получается результат с превышением разрядности мантиссы машинного слова, возвращают приближенное число.
Приближенные числа могут содержать верные, сомнительные и неверные цифры.
Неверные цифры при вычислениях влияют на точность и иногда могут приводить совершенно к неправильным результатам [3].
В соответствие с теорией приближенных вычислений, для получения правильных результатов приближенные числа округляются таким образом, чтобы исключить неверные цифры [6].
Точность, которую пользователь хочет, или может получить при вычислениях, определяется количеством верных цифр, которые обеспечивает вычислительный алгоритм.
Любое двоичное число можно округлить до заданного количества двоичных цифр, отбрасывая лишние разряды.
Аналогично, любое десятичное число можно округлить до требуемого количества десятичных цифр, отбрасывая лишние цифры.
Нельзя простым отбрасыванием лишних двоичных цифр в двоичном числе округлить его десятичный эквивалент до заданного количества десятичных цифр, поскольку уменьшение разрядности двоичного эквивалента десятичного числа приводит к увеличению числа неверных цифр в его десятичном эквиваленте.
Любое вещественное число, выраженное в форме десятичной дроби, может быть точно представлено в формате числа с плавающей точкой (ЧПТ), в котором мантисса является целым числом. Экспонента в ЧПТ будет указывать положение точки в этом числе.
Если число представлено в формате ЧПТ с целочисленной мантиссой, то мантисса и экспонента этого числа могут быть точно проконвертированы в двоичный код.
Формат, в котором мантисса десятичного ЧПТ представлена двоичным эквивалентом десятичной целочисленной мантиссы, а экспонента является двоичным эквивалентом степени числа 10 (база b=10), будем называть смешанным десятично — двоичным форматом (СДДФ).
Отличие СДДФ от двоичного формата ЧПТ в том, что экспонента в СДДФ равна степени базы b=10, в то время как экспонента двоичного формата ЧПТ равна двоичной степени базы b=2. Соответственно, для СДДФ число будет представлено как
, а для ЧПТ, в стандарте IEEE754, как 
.
Отличие СДДФ от двоично-десятичного формата (ДДФ или BCD) ЧПТ в том, что в ДДФ мантисса и экспонента представляют собой целые десятичные числа, в которых каждая цифра записана в виде байта или тетрады, в то время, как в СДДФ все десятичные числа выражаются их целыми двоичными эквивалентами.
Таким образом, любое десятичное вещественное число можно представить в СДДФ двоичным кодом с точностью до N значащих десятичных цифр.
Все арифметические операции над десятичными ЧПТ в СДДФ проводятся по правилам обычной арифметики, где все аргументы являются целыми числами.
Перед каждой арифметической операцией десятичное число представляется в формате СДДФ:[S,M,z,e]. Где S-код знака числа (0 или 1). M — двоичный целочисленный эквивалент мантиссы числа с количеством десятичных цифр N. Где N — точность вычислений. z — знак экспоненты, e -значение экспоненты. Такое представление является нормализованным представлением десятичного числа.
Например, для вычислений с точностью до N=7 значащих цифр, число 123,456 должно быть представлено как 1234560*10^-4.
Минимальное значение десятичной мантиссы числа для N=7 будет равно M=1000000.
Максимальное значение десятичной мантиссы числа для N=7 будет равно M=9999999.
Двоичный эквивалент максимального 7-ми разрядного числа 9999999 будет равен 100 110 001 001 011 001 111 111. Он содержит 24 двоичных разряда. Следовательно, для представления десятичных мантисс в диапазоне от 1000000 до 9999999 требуется двоичный 24-разрядный регистр.
Если в 32-х разрядном двоичном машинном слове, в котором 24 разряда отвести под мантиссу, один разряд отвести под знак числа S, один разряд под знак экспоненты z, а также 6 разрядов под экспоненту, то в таком СДДФ могут быть представлены десятичные вещественные числа с точностью до N=7 значащих десятичных чисел. Абсолютные значения этих чисел лежат в диапазоне от 1000000*10^-64 до 9999999*10^64.
После каждой арифметической операции десятичная мантисса числа должна быть нормализована и округлена до ближайшего целого. Для этого полученный двоичный эквивалент мантиссы числа, при необходимости, должен быть умножен или разделен на двоичный эквивалент числа 10 в такой степени, чтобы количество цифр десятичного эквивалента мантиссы стало равно величине N. Полученное таким образом число должно быть округлено до ближайшего целого.
Пример.
Найти с точностью до N=7 результат выражения (9675,423*10^2-9,675421*10^5)*10^6 — 199992
Вычисленное вручную, или на калькуляторе Windows, это выражение будет равно числу 8,000000
Запишем операнды в нормализованном виде:
В СДДФ эти операнды будут представлены как:
Найдем разность S=A-B. Поскольку экспоненты операндов A и B одинаковы, найдем мантиссу их разности:
Для нормализации мантиссы S надо умножить ее на 10^6, одновременно экспоненту надо уменьшить на 6. Тогда S =2*1000000=2000000*10^-7
Вычислим произведение P=D*C. Для этого перемножим мантиссы сомножителей и сложим экспоненты:
M= 2000000*10^-7*1000000*10*0=2000000000000*10^-7
После нормализации мантиссы получим P=2000000 *10^-1.
Результат R вычисления будет равен:
R=P-D=2000000 *10^-1-1999920*10^-1=80*10^-1
После нормализации получим R = 8000000*10^-6.
Для сравнения, вычисление этого выражения в Excel дает результат R = 8,0000698E+00.
Автором разработан алгоритм калькулятора в СДДФ, осуществляющий сложение, вычитание, умножение и деление десятичных чисел с точностью до 18-ти значащих цифр. Для подтверждения правильности алгоритма была написана программа на C++. Поскольку автор не является профессиональным программистом, разработанная программа предназначена только для исследования алгоритма вычислений.
Ниже, для примера, представлен скриншот, демонстрирующий вычисление следующего выражения:
Для проверки быстродействия, в цикле была запущена операция умножения двух 18-ти разрядных чисел. Программа запускалась на компьютере Intel® Core(TM) i3-4330 CPU@3.50GHz 3.50 GHz. ОЗУ 8,0 ГБ. Тип системы: 64-разрядная. Скорость получилась равной ≈ 2.4*10^6 умножений в секунду.
Сравнить с быстродействием калькуляторов Windows и Excel я пока не могу, не хватает образования:(. Что же касается точности вычислений, то она такая же, как если бы расчеты велись вручную.
Литература:
В этих алгоритмах использована двоичная арифметика, регламентированная стандартом IEEE754. Для проверки работы алгоритмов была разработана тестовая программа на C++, реализующая 18-ти разрядный десятичный калькулятор.
Поскольку объем материала превышает формат поста, я изложил основные моменты в виде тезисов. Назовем этот пост «Майскими тезисами»:(.
Итак.
Известно, что
Привычная для пользователя арифметика, это десятичная арифметика.
Существуют также b-ичные арифметики, где b- база системы счисления, принимающая любое ненулевое значение [5].
Для отображения чисел в разных масштабах используется запись чисел с плавающей точкой в виде произведения мантиссы и некоторой произвольной степени базы. Это, так называемая, экспоненциальная запись.
Если степень числа фиксирована и мантисса числа является целым числом, то такой формат называется форматом с фиксированной точкой. Частным случаем формата с фиксированной точкой является число, в котором степень равна нулю. Такой формат является форматом целого числа.
Если мантисса представляет собой дробное число в b-ичной системе счисления с целой частью c≠0 и c < b, то такое число называется нормализованным.
Несмотря на то, что по своей физической природе числа являются приближенными, для вычислительного устройства это точные числа и операции над ними устройство должно производить с заданной пользователем точностью.
Под точными вычислениями в арифметике подразумевают получение результата с заданным количеством верных значащих цифр после точки [6].
Все вычисления в компьютере производятся в двоичном виде. Для них база b = 2.
Поскольку двоичная и десятичная системы счисления несоизмеримы, то при конвертации десятичных вещественных чисел в двоичный код чаще всего мы получаем приближенное значение двоичного эквивалента десятичного числа. Поэтому, при переводе десятичных чисел в двоичные возникают погрешности представления.
Десятичные числа, которые имеют точный двоичный эквивалент, называют представимыми.
Десятичные числа, которые не имеют точного двоичного эквивалента, называются непредставимыми.
Все целые десятичные числа представимы, если количество значащих цифр в их двоичном эквиваленте не превышает разрядную сетку области машинного слова, в которую они записываются.
Чем большим количеством двоичных разрядов представлен десятичный эквивалент числа в двоичном виде, тем меньше ошибка представления. Этим объясняется стремление постоянно наращивать разрядность операционного регистра процессора.
Любое десятичное число, двоичный эквивалент которого содержит количество значащих цифр, превышающее разрядную сетку машинного слова, может быть представлено только приближенно.
Арифметические действия, в результате которых получается результат с превышением разрядности мантиссы машинного слова, возвращают приближенное число.
Приближенные числа могут содержать верные, сомнительные и неверные цифры.
Неверные цифры при вычислениях влияют на точность и иногда могут приводить совершенно к неправильным результатам [3].
В соответствие с теорией приближенных вычислений, для получения правильных результатов приближенные числа округляются таким образом, чтобы исключить неверные цифры [6].
Точность, которую пользователь хочет, или может получить при вычислениях, определяется количеством верных цифр, которые обеспечивает вычислительный алгоритм.
Любое двоичное число можно округлить до заданного количества двоичных цифр, отбрасывая лишние разряды.
Аналогично, любое десятичное число можно округлить до требуемого количества десятичных цифр, отбрасывая лишние цифры.
Нельзя простым отбрасыванием лишних двоичных цифр в двоичном числе округлить его десятичный эквивалент до заданного количества десятичных цифр, поскольку уменьшение разрядности двоичного эквивалента десятичного числа приводит к увеличению числа неверных цифр в его десятичном эквиваленте.
Любое вещественное число, выраженное в форме десятичной дроби, может быть точно представлено в формате числа с плавающей точкой (ЧПТ), в котором мантисса является целым числом. Экспонента в ЧПТ будет указывать положение точки в этом числе.
Если число представлено в формате ЧПТ с целочисленной мантиссой, то мантисса и экспонента этого числа могут быть точно проконвертированы в двоичный код.
Новое
Формат, в котором мантисса десятичного ЧПТ представлена двоичным эквивалентом десятичной целочисленной мантиссы, а экспонента является двоичным эквивалентом степени числа 10 (база b=10), будем называть смешанным десятично — двоичным форматом (СДДФ).
Отличие СДДФ от двоичного формата ЧПТ в том, что экспонента в СДДФ равна степени базы b=10, в то время как экспонента двоичного формата ЧПТ равна двоичной степени базы b=2. Соответственно, для СДДФ число будет представлено как
, а для ЧПТ, в стандарте IEEE754, как .Отличие СДДФ от двоично-десятичного формата (ДДФ или BCD) ЧПТ в том, что в ДДФ мантисса и экспонента представляют собой целые десятичные числа, в которых каждая цифра записана в виде байта или тетрады, в то время, как в СДДФ все десятичные числа выражаются их целыми двоичными эквивалентами.
Таким образом, любое десятичное вещественное число можно представить в СДДФ двоичным кодом с точностью до N значащих десятичных цифр.
Все арифметические операции над десятичными ЧПТ в СДДФ проводятся по правилам обычной арифметики, где все аргументы являются целыми числами.
Перед каждой арифметической операцией десятичное число представляется в формате СДДФ:[S,M,z,e]. Где S-код знака числа (0 или 1). M — двоичный целочисленный эквивалент мантиссы числа с количеством десятичных цифр N. Где N — точность вычислений. z — знак экспоненты, e -значение экспоненты. Такое представление является нормализованным представлением десятичного числа.
Например, для вычислений с точностью до N=7 значащих цифр, число 123,456 должно быть представлено как 1234560*10^-4.
Минимальное значение десятичной мантиссы числа для N=7 будет равно M=1000000.
Максимальное значение десятичной мантиссы числа для N=7 будет равно M=9999999.
Двоичный эквивалент максимального 7-ми разрядного числа 9999999 будет равен 100 110 001 001 011 001 111 111. Он содержит 24 двоичных разряда. Следовательно, для представления десятичных мантисс в диапазоне от 1000000 до 9999999 требуется двоичный 24-разрядный регистр.
Если в 32-х разрядном двоичном машинном слове, в котором 24 разряда отвести под мантиссу, один разряд отвести под знак числа S, один разряд под знак экспоненты z, а также 6 разрядов под экспоненту, то в таком СДДФ могут быть представлены десятичные вещественные числа с точностью до N=7 значащих десятичных чисел. Абсолютные значения этих чисел лежат в диапазоне от 1000000*10^-64 до 9999999*10^64.
После каждой арифметической операции десятичная мантисса числа должна быть нормализована и округлена до ближайшего целого. Для этого полученный двоичный эквивалент мантиссы числа, при необходимости, должен быть умножен или разделен на двоичный эквивалент числа 10 в такой степени, чтобы количество цифр десятичного эквивалента мантиссы стало равно величине N. Полученное таким образом число должно быть округлено до ближайшего целого.
Пример.
Найти с точностью до N=7 результат выражения (9675,423*10^2-9,675421*10^5)*10^6 — 199992
Вычисленное вручную, или на калькуляторе Windows, это выражение будет равно числу 8,000000
Запишем операнды в нормализованном виде:
A=9,675423*10^5= 9675423*10^-1
B= 9675,421*10^2 = 9675421*10^-1
C=1000000 = 1000000*10^0
D = 1999920*10^-1В СДДФ эти операнды будут представлены как:
A=[0, 9675423,1, 1]
B=[0,9675421,1, 1]
C=[0, 1000000,0, 0]
D=[0, 1999920,1, 1]Найдем разность S=A-B. Поскольку экспоненты операндов A и B одинаковы, найдем мантиссу их разности:
9675423-9675421=2Для нормализации мантиссы S надо умножить ее на 10^6, одновременно экспоненту надо уменьшить на 6. Тогда S =2*1000000=2000000*10^-7
Вычислим произведение P=D*C. Для этого перемножим мантиссы сомножителей и сложим экспоненты:
M= 2000000*10^-7*1000000*10*0=2000000000000*10^-7
После нормализации мантиссы получим P=2000000 *10^-1.
Результат R вычисления будет равен:
R=P-D=2000000 *10^-1-1999920*10^-1=80*10^-1
После нормализации получим R = 8000000*10^-6.
Для сравнения, вычисление этого выражения в Excel дает результат R = 8,0000698E+00.
Автором разработан алгоритм калькулятора в СДДФ, осуществляющий сложение, вычитание, умножение и деление десятичных чисел с точностью до 18-ти значащих цифр. Для подтверждения правильности алгоритма была написана программа на C++. Поскольку автор не является профессиональным программистом, разработанная программа предназначена только для исследования алгоритма вычислений.
Ниже, для примера, представлен скриншот, демонстрирующий вычисление следующего выражения:
1,23456789098765432*10^8 * 9,87654321234567891*10^(-9) - 1,2193263123914037*10^0≈ 3.0*10^(-17)
Для проверки быстродействия, в цикле была запущена операция умножения двух 18-ти разрядных чисел. Программа запускалась на компьютере Intel® Core(TM) i3-4330 CPU@3.50GHz 3.50 GHz. ОЗУ 8,0 ГБ. Тип системы: 64-разрядная. Скорость получилась равной ≈ 2.4*10^6 умножений в секунду.
Сравнить с быстродействием калькуляторов Windows и Excel я пока не могу, не хватает образования:(. Что же касается точности вычислений, то она такая же, как если бы расчеты велись вручную.
Литература:
