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

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

Пусть A, N, e три целых положительных числа многократной точности, причем A < N. Тогда для любого e при вычислении Ae(mod N)C, результат редукции C{1,N1}. Если e представить nразрядным двоичным вектором, то всю операцию возведения в степень можно свести к чередованию операций вида A*B modulo N и B*B modulo N, где 0 < B < N1. Таким образом, во всех дальнейших рассуждениях e будет представляться только как двоичная строка. Кроме того, числа A, B, N, а также P частичное произведение и S текущий результат будут представляться nбитовыми двоичными векторами, например, N[1,n], где N[1] и N[n] младший и старший биты N соответственно.

Алгоритм использует вычислительную систему с фиксированной длиной слова, то есть 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 такой системы будет ограничено длиной машинного слова λ и цифры такой системы имеют вид 0,1,...,r1 (r выбирается как целое положительное основание с неотрицательной базой). При этом n и m связаны соотношением n=s*m, где s=log2r (в дальнейших рассуждениях log логарифм по основанию 2). Наиболее целесообразно выбрать основание r=2λ как наиболее экономное представление чисел в машине, ибо при r < 2λ на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоичнодесятичном коде требует на 20 % большего объема памяти, чем двоичное представление тех же чисел.

Тем не менее, иногда полезно представлять ситуацию, когда r=10 или r=10k, например, при отладке программ.

Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута, основание r следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до r=2λ1, для умножения до r=2λ/2. Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию r=2λ.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок