На этом шаге мы рассмотрим задачу перемножения длинных целых чисел без знака.

    Длинные целые числа используются в арифметике высокой точности (Д. Кнут. Т. 2), криптографическом кодировании сообщений (шифровании). При этом длина чисел (т.е. количество цифр в записи числа) может достигать нескольких сотен и более. Арифметические операции (сложение, вычитание, умножение, деление) над длинными числами не могут выполняться компьютером за один шаг. Любая такая операция должна реализовываться специально написанной процедурой.

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

    Наиболее естественным является простое расширение стандартного формата: если для записи числа требуется n цифр, то память для них выделяется в виде непрерывной области соответствующего размера.

    Предположим, что перемножается два числа U = u_nu_n-1u_n-2 ... u₃u₂u₁ и V = v_nv_n-1v_n-2 ... v₃v₂v₁. Результат имеет суммарную длину W = w_nw_n-1w_n-2 ... w₃w₂w₁. Числа записаны в позиционной системе счисления с основанием (базой) β: 0 <= u_i, v_i, w_i < b. При этом индекс единица соответствует младшей цифре в записи числа.

Алгоритм умножения 1 (классический)

    Этот алгоритм работает подобно тому, как производится умножение на бумаге. Числа представлены массивами цифр. Основание системы счисления b может быть как двоичным, b = 2, так и сколь угодно большим, например, занимающим машинное слово. Важно, чтобы перемножить или сложить цифры можно было одной машинной операцией (или малым их числом). Для представления цифр процедура использует некоторый тип Digit.

procedure SimpleMultiplication (U, V: superlongpositive; 
    var W: superlongpositive; n, m: integer); 
var     
   i, j: integer;
   S: DoubleDigit;  {Место для формирования двух цифр.} 
   C: Digit;   {Разряд переноса.}
begin 
   for i := 1 to n do 
     W[i] := 0; {Подготовка места для результата.}
   for j := 1 to m do         {Пo цифрам числа V.}
     begin 
         С := 0; {Сначала переноса нет.}
         for i := 1 to n do {Пo цифрам числа U.}
           begin 
               S := U[i]*V[j]+W[i+j-1]+C; 
               W[i+j-1] := S mod P; {Временное значение очередной цифры.}
               С := S div P; {Формирование разряда переноса.} 
           end;
         W[j + n] := С;   {Старшая цифра частичного произведения.}
     end;
end;

    Непосредственно видно, что сложность этого алгоритма равна O(n^m) или в случае сомножителей одинаковой длины - O(n²).

Алгоритм умножения 2 (оптимизированный по времени)

    Разделим задачу на подзадачи, разделив запись каждого из сомножителей на две части: U= U₂U₁, V=V₂V₁. При n-разрядных сомножителях длины U_i, V_i будут равны n/2. Индексу 1 соответствует младшая половина, а индексу 2 - старшая. Иначе можно записать U = U₂00..00 + U₁ = U₂β^n/2 + U₁.

    Произведение UV = (U₂β^n/2 + U₁)(V₂β^n/2 + V₁) = UVβⁿ + U₂V₁β^n/2 + U₁V₂β^n/2 + U₁V₁. Вычисление произведения предлагаемым способом требует четырех умножений чисел половинной длины, трех сложений и трех умножений на величину β^q. Умножения на степень β равносильны сдвигу и требуют времени O(n). То же можно сказать о сложности аддитивных операций.

    Четырех умножений чисел оказывается слишком много: log₂4 = 2, сложность рекурсивного алгоритма будет равна O(n²).

    Но можно немного преобразовать расчетную формулу:

UV = U₂V₂(βⁿ + β^n/2) + (U₂ - U₁)(V₁-V₂)β^n/2 + U₁V₁(β^n/2+1)

    Она содержит только три умножения. Очевидный алгоритм, строящийся по этой формуле, описывается уравнением для функции сложности:

Т(n) = 3Т(n/2) + βⁿ,

его решение Т(n) = O(n^log3) = O(n^1,58), что значительно лучше классического алгоритма.

    На следующем шаге мы рассмотрим возведение целого числа без знака в положительную целую степень.

Предыдущий шаг Содержание Следующий шаг