BC/NW 2007, №1, (10) :16.13
Библиотека,
реализующая вычисления в числах, представленных в знакоразрядной СИСТЕМЕ
СЧИСЛЕНИЯ
Д.А. Орлов, Ш.А. Оцоков
(Москва, Московский энергетический институт (технический университет), Россия)
В настоящее время имеется множество задач, где
необходимо вычислять результат с большой точностью. Один из способов её
достижения – увеличение количества разрядов числа. Но увеличение количества
разрядов приводит к увеличению времени вычислений. Для достижения ускорения
возможно применение аппаратной реализации. Однако, и в этом случае время
сложения чисел будет линейно зависеть от количества разрядов числа, так как для
вычисления значения некоторого разряда, необходимо знать перенос из
предыдущего. Поэтому для ускорения вычислений необходимо изменить способ
представления чисел. Один из возможных вариантов – знакоразрядная система
счисления [1].
В знакоразрядной системе счисления значения разрядов
числа могут принимать значения от –(q-1) до q-1, где q – основание системы счисления. В обычной позиционной
системе счисления числа могут принимать только значения от 0 до q-1. Достоинством знакоразрядной системы счисления
является то, что перенос, возникающий при сложении, распространяется не далее,
чем на следующий разряд. Это свойство позволяет складывать и вычитать числа
любой длины при аппаратной реализации за 3 такта [1].
Для моделирования и демонстрации работоспособности
вычислений в числах в знакоразрядной системе счисления была разработана
программная библиотека. В ней реализованы основные арифметические операции над
числами, представленными в знакоразрядоной системе счисления: сложение,
вычитание, умножение, деление, взятие остатка. Реализованы также алгоритм
перевода чисел в обычную позиционную систему счисления, ввод и вывод чисел.
Библиотека написана на языке C++ в среде Visual Studio 2003.
Литература
1. A. H. Fahmy,
Redundant digit floating point system PhD thesis,