Представление чисел
Пусть A, N, e - три целых положительных числа многократной точности, причем A<N. Тогда для любого e при вычислении Ae(modN)ºC, результат редукции CÎ{1,N-1}. Если e представить n-разрядным двоичным вектором, то всю операцию возведения в степень можно свести к чередованию операций вида A*B modulo N и B*B modulo N, где 0<B<N-1 [Кн, стр.482-510]. Таким образом, во всех дальнейших рассуждениях e будет представляться только как двоичная строка. Кроме того, числа A, B, N, а также P - частичное произведение и S - текущий результат будут представляться n-битовыми двоичными векторами, например, N[1,n], где N[1] и N[n] - младший и старший биты N
соответственно.
Алгоритм Р (при разработке и доказательстве его правильности использованы результаты работы [Bk]), реализует вычислительную систему с фиксированной длиной слова, то есть A, B, N, P и S будут также рассматриваться как векторы A[1,m], B[1,m], N[1,m], P[1,m'] и S[1,m'], где каждый элемент вектора (элемент одномерного массива) есть цифра r-ичной системы счисления, m'=m+h, величина h будет изменяться в зависимости от вида алгоритма. Основание r
такой системы будет ограничено длиной машинного слова l и цифры такой системы имеют вид 0,1,...,r-1 (r выбирается как целое положительное основание с неотрицательной базой). При этом n и m
связаны соотношением n=s*m, где s=log2r (в дальнейших рассуждениях log - логарифм по основанию 2). Наиболее целесообразно выбрать основание r=2l как наиболее экономное представление чисел в машине, так как при r<2l на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоично-десятичном коде требует на 20 % большего объема памяти, чем двоичное представление тех же чисел.
Тем не менее, иногда полезно представлять ситуацию, когда r=10 [Кн, стр.283] или r=10k, например, при отладке программ.
Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута [Кн, стр.282-302], основание r
следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до r=2l-1, для умножения - до r=2l/2. Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию r=2l.
