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


См. также:

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

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

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

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

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

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

    Пронумеруем разряды «длинных» чисел, например, ai или bi, и положим 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 на сумму вида 2n + 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 :