Арифметика и числовые алгоритмы

Алгоритм Карацубы

Идея, сложность

Алгоритм по своей сути рекурсивный и основывается на сведении задачи перемножения многочленов степени 2n к трем задачам умножения многочленов степени n:

(1)

Вычисляются перемножением многочлены , , . Последний в свою очередь равен . Таким образом, вычитанием найдем и второе выражение в правой части формулы (1).

Оценим получающуюся сложность

, где в включены все производимые вычитания и сложения многочленов.

Итого, как это строго доказано в [1],

Реализация, оптимизации

С реализацией проблем возникнуть не должно. Ключевой оптимизацией является использование «наивного» алгоритма для маленьких значений n. Это значение, после которого n называется «маленьким» зависит от разных факторов. В качестве упражнения рекомендуется дома его узнать для своего компьютера, а также для популярных тестирующих систем on-line. Еще в реализациях часто используется много операций копирования, обнуления и выделения памяти. Это вполне можно свести к минимуму.

Приведем отрывки кода (взятые из авторского решения первой из разбираемых задач), достаточно оптимально реализующего описанный алгоритм на языке Delphi.

type tpoly=array [0..MaxD] of integer;

     ppoly=^tpoly;

 

procedure add (var a:tpoly; const b:tpoly; bd:integer; const c:tpoly; cd:integer);

var i:integer;

begin

   for i:=0 to min (bd, cd) do

      a[i]:=b[i]+c[i];

   if bd<cd then

      move (c[bd+1], a[bd+1], (cd-bd)*sizeof (integer))

   else

      move (b[cd+1], a[cd+1], (bd-cd)*sizeof (integer))

end;

procedure mul (var a:tpoly; const b, c:tpoly; d:integer);

var i, j, k:integer;

    x, y, z:array of integer;

begin

   if d<50 then begin

      for i:=0 to d do

         for j:=0 to d do

            inc (a[i+j], b[i]*c[j]);

      exit;

   end;

   k:=d shr 1 + 1;

   mul (a, b, c, k-1);

   mul (ppoly (@a[k shl 1])^, ppoly (@b[k])^, ppoly (@c[k])^, d-   k);

   setlength (x, k);

   add (ppoly (@x[0])^, b, k-1, ppoly (@b[k])^, d-k);

   setlength (y, k);

   add (ppoly (@y[0])^, c, k-1, ppoly (@c[k])^, d-k);

   setlength (z, (k-1) shl 1 + 1);

   mul (ppoly (@z[0])^, ppoly (@x[0])^, ppoly (@y[0])^, k-1);

   sub (ppoly (@z[0])^, ppoly (@z[0])^, (k-1) shl 1, ppoly (@a[0])^, (k-1) shl 1);

   sub (ppoly (@z[0])^, ppoly (@z[0])^, (k-1) shl 1, ppoly (@a[k shl 1])^, (d-k) shl 1);

   add (ppoly (@a[k])^, ppoly (@a[k])^, (k-1) shl 1, ppoly (@z[0])^, (k-1) shl 1);

end;

Видно, что этот код довольно некрасив, и хотя идейно прост, может уйти много времени на написание и отладку. К сожалению, здесь нельзя сказать, что такие оптимизации обычно не нужны, потому что если в задаче требуется алгоритм Карацубы, то ограничения чаще всего достаточно жесткие.

И напоследок не забудьте про то, что числа ― это не совсем многочлены. Типичной ошибкой является неправильный выбор основания системы счисления. Основание системы счисления, которое не вызовет переполнение используемых типов в некоторых реализациях может зависеть от длины перемножаемых чисел. Рекомендуется избегать таких реализаций, это возможно без больших потерь производительности.