Длинная арифметика. Сложение и вычитание

Складывать и вычитать учат с первого класса школы. И в отличие от умножения ничего более эффективного, чем “первоклассный” школьный алгоритм “в столбик” и не надо придумывать.. Итак, ниже приведен алгоритм вычисления суммы С =А + В чисел А и В длины n цифр. При этом помимо n – значного результата С возвращается также бит переноса из старших разрядов d.

Алгоритм 1.1. Сложение длинных чисел

1.       d := 0;

2.       для i = 0… n-1 выполнить шаги 3-5;

3.       T := A_i+B_i+d;

4.       C_i = LODIGIT(T);

5.       d := HIDIGIT(T);

6        конец.

Здесь и далее:

- Т – число длины 2m битов (TWODIGIT), необходимое по причине того, что результат операции над m-битными числами имеет длину большую чем m;

- d — число длины m битов (DIGIT), используемое для хранения бита переноса разряда.

Алгоритм вычитания известный из 1-го класса столь же прост. Итак,С = A-B, длина С, А, В равна n цифр, d – заем старшего разряда.

Алгоритм 1.2. Вычитание длинных чисел.

1.       d := 0;

2.       для i = 0… n-1 выполнить шаги 3-6;

3.       T := A_i-B_i-d;

4.       C_i = LODIGIT(T);

5.       если HIDIGIT(T) = 0, то d := 0;

6.       иначе d :=1;

7.       конец.