Краткий теоретический материал по арифметике длинных чисел

См. также:

‹ Зайдельман Я.Н. "Буки программирования" ‹ Окулов С.М. "Длинная" арифметика ‹ Длинные числа и операции с ними (сборник алгоритмов)

Структуры данных

В зависимости от прикладных задач, для представления «длинных» чисел используются либо статические векторы (массивы), либо динамические структуры (списки).

Алгоритмы вычисления арифметических операций

Чтобы реализовать базовые арифметические операцие +, −, x, / над «длинными» числами, следует опираться на стандартные методы вычисления сложения/вычитания/умножения «в столбик» и деления «уголком». При этом понадобятся вспомогательные подпрограммы:

обнуление «длинного» числа ( := 0 )
присваивание «длинных» чисел друг другу ( := )
обмен значений «длинных» чисел (swap)
определение количества разрядов «длинного» числа (length)
сравнение «длинных» чисел ( <, =, >, <> )
взятие абсолютного значения «длинного» числа (abs)
изменение знака «длинного» числа (inv)
сдвиг «длинного» числа на n разрядов вправо (shiftr)
сдвиг «длинного» числа на n разрядов влево (shiftl)

Пронумеруем разряды «длинных» чисел, например, a_i или b_i, и положим M равным основанию системы счисления.

Сложение

Алгоритм «длинного» сложения основан на методе сложения в «столбик». При этом циклически, начиная с младших разрядов, производится сложение с переносом.

{ Сложение с := a + b }
cf := 0;
L  := max ( length (a), length (b) );
i  := 0;
while ( i < L ) or ( cf <> 0 ) do
begin
  t := a[i] + b[i] + cf;
  if M <= t then                     { c[i] := ( a[i] + b[i] + cf ) mod M }
  begin                              { cf   := ( a[i] + b[i] + cf ) div M }
    c[i] := t - M
    cf   := 1;
  end
  else
  begin
    c[i] := t;
    cf   := 0;
  end;
  i := i + 1;
end;

Проверка работы алгоритма сложения

Введите неотрицательные целые аргументы a и b:

a :
+
b :

c :

Вычитание

Вычитание двух неотрицательных чисел также можно реализовать «в столбик».

{ Вычитание с := a - b }
L    := max ( length (a), length (b) );
sign := false;
if a < b then
begin
  swap ( a, b );
  sign   := true;
end
i  := 0;
cf := 0;
while ( i < L ) or ( cf <> 0 ) do
begin
  t := b[i] + cf;
  if a[i] < t then
  begin
    c[i] := M + a[i] - t;
    cf   := 1;
  end
  else
  begin
    c[i] := a[i] - t;
    cf   := 0;
  end;
  i := i + 1;
end;
if sign then
  inv (c);

Проверка работы алгоритма вычитания

Введите неотрицательные целые аргументы a и b:

a :
–
b :

c :

Деление на 2

Для обеспечения работы алгоритмы умножения следует реализовать деление неотрицательного «длинного» числа на 2.

{ Деление на 2 a := a div 2 }
cf := 0;
i  := length (a);
while 0 <= i do
begin
  t    := a[i] + cf*M;
  a[i] := t div 2;
  cf   := t mod 2;
  i    := i - 1;
end;

Проверка работы алгоритма деления на 2

Введите неотрицательное целое:

a :

c :

Умножение

Для реализации «длинного» умножения можно воспользоваться методом разложения произведения ab на сумму вида 2ⁿ + q. Для наглядности можно привести следующие тождества:

ab = (2a)(b/2), если b — чётно, и

ab = a(b − 1) + a, если b — нечётно.

Тогда алгоритм умножения неотрицательных «длинных» чисел можно выразить через реализованный ранее алгоритм сложения/вычитания и алгоритм деления на 2.

{ Умножение p := a * b }
p := 0;
if ( a < b ) then
  { если в качестве b выбрать меньшее число, то эффективность выше }
  swap (a, b);
while 0 < b do
begin
  if b mod 2 = 0 then
  begin
    a := a + a;      {  a := 2*a; }
    b := b / 2;
  end
  else
  begin
    b := b - 1;
    p := p + a;
  end;
end;

Проверка работы алгоритма умножения

Введите неотрицательные целые аргументы a и b:

a :
x
b :

c :

Деление

Деление неотрицательных «длинных» чисел «уголком» выглядит не столь эффектно, как реализованное выше умножение. Реализовать деление более оптимально можете попробовать самостоятельно.

{ Деление p := a div b; q := a mod b; }
 
q  := a;   { спасаем исходное a, и в q будет остаток от деления }
La := length ( q );
Lb := length ( b );
sh := La - Lb;
p  := 0;
 
while b <= q do
begin
  o  := 1;
  t  := shiftr ( q, sh );
  if t < b then
  begin
    sh := sh - 1;
    t  := shiftr ( q, sh );
    o  := 0;
  end;
 
  { подбор очередной цифры частного }
  d  := 9;
  m  := b * d;
  while t < m do
  begin
    d := d - 1;
    m := b * d;
  end;
 
  q  := q - shiftl ( m, sh );
  p  := shiftl ( p, 1 ) + d;
 
  if q < b then
    shiftl ( p, sh )
  else
    shiftl ( p, La - length (q) - o - 1 );
 
  La := length ( q );
 
end;

Проверка работы алгоритма деления

Введите неотрицательные целые аргументы a и b:

a :
/
b :

c :