9.2.1 Представление чисел

Пусть  -- три целых положительных числа многократной точности, причем . Тогда для любого при вычислении , результат редукции . Если представить -разрядным двоичным вектором, то всю операцию возведения в степень можно свести к чередованию операций вида и , где [Кнут, стр. 482-510]. Таким образом, во всех дальнейших рассуждениях будет представляться только как двоичная строка. Кроме того, числа , а также  -- частичное произведение и  -- текущий результат будут представляться -битовыми двоичными векторами, например, , где и -- младший и старший биты соответственно.

Так как в интеллектуальных карточках, как правило, из-за ограниченных размеров рабочего пространства используется вычислительная система с фиксированной длиной слова, то и будут также рассматриваться как векторы , , , и , где каждый элемент вектора (элемент одномерного массива) есть цифра -ичной системы счисления, , величина будет изменяться в зависимости от вида алгоритма. Основание такой системы будет ограничено длиной машинного слова , т. е. и цифры такой системы имеют вид . При этом и связаны соотношением , где (в дальнейших рассуждениях  -- логарифм по основанию 2). Наиболее целесообразно выбрать основание как наиболее экономное представление чисел в машине, ибо при на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоично-десятичном коде требует на 20% большего объема памяти, чем двоичное представление тех же чисел [Ш]. Тем не менее, иногда полезно представлять ситуацию, когда [Кнут, стр. 283] или , например, при отладке программ.

Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута [Кнут, стр. 282-302], основание следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до , для умножения -- до . Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию .

Далее будет показано, что для ускоренного суммирования могут использоваться избыточные системы счисления. В [Pa], например, предложена обобщенная знаковая система для представления широкого класса избыточных числовых систем. Однако сегодня находят применение лишь немногие из них. Так, в [Bak] для выполнения сложения в случае явного представления сохраняемого переноса (CARRY-SAVE ADDITIONS -- CSAs) в алгоритме используется система с основанием , которая определена на множестве . В [Ta] предложен высокоскоростной алгоритм умножения -разрядных чисел со скоростью пропорциональной , где используется система, определенная на множестве . Такая же система для кодирования используется в ускоренном алгоритме в [CMY]. Для представления чисел в таких системах требуется в два раза больше вентилей, чем для представления чисел в обычном двоичном виде.