Алгоритм быстрого умножения Тоома—Кука, описываемый Кнутом, зиждется на четырех основных идеях[31]. Вот первая из них. Пусть нам известен способ выполнения некоторой операции над исходными данными размера n за время T(n). Если эту операцию удастся разбить на r частей, выполнение каждой из которых займет менее чем T(n)/r шагов, то такое разбиение позволит улучшить общее время, если, конечно, считать, что вспомогательные организационные расходы не сведут экономию на нет. Пусть, далее, каждая из r частей есть применение того же алгоритма к исходным данным длины n/r и каждая часть может быть разбита аналогичным образом. Тогда можно продолжать это разбиение, пока мы не получим столь короткие исходные данные, что вычисления для них станут тривиальными и займут лишь небольшой фиксированный отрезок времени. Этот принцип разделяй и властвуй обычно дает выигрыш во времени работы алгоритма по крайней мере в log n раз; так, классический метод умножения требует времени n?, и его можно свести к , что существенно лучше при больших n (не забывайте, что у обеих функций стоимости имеются постоянные множители).

Остальные три идеи касаются чисел и действий над многочленами. Во-первых, заметим, что, если число U имеет длину n битов и записывается в двоичном виде как

u_n?1u_n?2…u₂u₁u₀,

причем n делится на r + 1, то U можно также записать в виде

U_r2^rn/(r+1) + U_r?12^(r?1)n/(r+1) + … + U₁2^n/(r+1) + U₀,

где каждое U_i есть блок из n/(r + 1) битов исходного представления U. Фактически U = U(2^{n/(r + 1)}), где многочлен U(x) есть

U_rx^r + U_r?1x^r?1 + … + U₁x + U₀.

Во-вторых, мы видим, что если U и V — два n-разрядных числа, записанных в виде такого многочлена, то их произведение W дается формулой

W = UV = U(2^{n/(r + 1)})V(2^{n/(r + 1)}) = W(2^{n/(r + 1)})

и если бы мы смогли найти хотя бы коэффициенты W(х), то вычислить W по W было бы сравнительно просто; для этого понадобились бы только сдвиги, сложения и умножения чисел из n/r битов. В-третьих, к счастью, W(х) — многочлен степени 2r и его можно найти с помощью интерполяции его значений в точках 0, 1, 2, …, 2r?1, 2r. Эти значения равны просто U(0), V(0), U(1), V(1), …, U(2r), V(2r). Более того, для вычисления всех этих многочленов и интерполяции требуется умножать числа только из n/r битов. Представляется, что эти действия подпадают под принцип «разделяй и властвуй».

Алгоритм Тоома—Кука весьма сложен, поэтому мы не будем подробно объяснять его; за этим можно обратиться к книге Кнута. Все же необходимо сообщить основные идеи и обозначения. Длинные числа должны быть как-то представлены; будем писать [p, u] для обозначения числа u из p битов. Вероятно, внутреннее представление [p, u] будет некоторой разновидностью списка или цепочки. Кроме основного алгоритма нам понадобятся подпрограммы для сложения и вычитания длинных чисел (используйте стандартный ручной метод сложения слева направо), умножения длинного числа на короткое (небольшое) число, деления длинного числа на короткое, сдвига длинного числа путем приписывания нулей справа и для разбиения длинного числа [p, u] на более короткие длинные числа [p/(r + 1), u_r], [p/(r + 1), u_r?1], …, [p/(r + 1), u₀], как описано выше. Кроме подпрограмм, работающих непосредственно с числами, алгоритм использует четыре стека для хранения промежуточных частичных результатов и несколько временных переменных, поэтому требуются подпрограммы для выполнения некоторых действий над стеком, а также подпрограммы для выделения и освобождения памяти под длинные числа. При написании всяческих вспомогательных подпрограмм черновой работы может оказаться предостаточно.

Исходными данными служат два положительных длинных числа [n, u] и [n, v]; результатом — их произведение [2n, uv]. Используются четыре стека U, V, W и С, в которых при выполнении алгоритма будут храниться длинные числа, и пятый стек, содержащий коды временно приостановленных операций (имеется всего три кода, и для их представления можно воспользоваться малыми целыми числами). Массивы q и r целых чисел имеют индексы от 0 до 10; необходимо выделить память для этих двух массивов и для еще нескольких временных переменных, упомянутых в алгоритме.

1. (Начальная установка.) Сделать все стеки пустыми. Присвоить К значение 1, q₀ и q₁ — значение 16, r₀ и r₁ — значение 4, Q — значение 4 и R — значение 2.

2. (Построение таблицы размеров). Пока К < 10 и q_K?1 + q_K ? n, выполнять следующие вычисления. Изменить К на К + 1, Q — на Q + R; если (R + 1)? ? Q, то изменить R на R + 1; установить q_K равным 2^Q и r_K равным 2^R. Если цикл оканчивается из-за К = 10, то остановиться, выдав сообщение об ошибке — число битов n слишком велико, массивы q и r переполнились. В противном случае присвоить k значение K. Поместить [q_K + q_K?1, v] и за ним [q_K?1 + q_K, u] в стек С (вероятно, потребуется добавить к [n, u] и [n, v] слева нули). Поместить в управляющий стек код стоп.

3. (Главный внешний цикл.) Пока управляющий стек не пуст, выполнять шаги с 4-го по 18-й. Если на этом шаге управляющий стек окажется пустым, то остановиться с сообщением об ошибке; в управляющем стеке должен быть по крайней мере один элемент.

4. (Внутренний цикл разбиения и и v.) Пока к > 1, выполнять шаги с 5-го по 8-й.

5. (Установка параметров разбиения.) Установить k равным k ? 1, s равным q_k, t равным r_k и р равным q_k?1 + q_k.

6. (Разбиение верхнего элемента стека С.) Длинное число [q_k + q_k+1, u] на вершине С следует рассматривать как t + 1 чисел длиной s битов каждое. Разбить [q_k + q_k+1, u] на длинные числа [s, U_t], [s, U_t?1], …, [s, U₁], [s, U₀]. Эти t + 1 чисел являются коэффициентами многочлена степени t, который следует вычислить в точках 0,1, …, 2t ? 1, 2t no правилу Горнера. Для i = 0, 1, …, 2t ? 1, 2t вычислить [р, X_i] по формуле

(…([s, U_t]i + [s, U_t?1])i+ … + [s, U₁])i + [s, U₀]

и сразу поместить [р, X_i] в стек U. Для выполнения умножений можно использовать подпрограмму умножения длинных чисел на короткие; никакой промежуточный или окончательный результат не потребует более p битов. Удалить [q_k + q_k+1, u] из стека С.

7. (Продолжение разбиения.) Выполнить над числом [m, v], находящимся сейчас на вершине стека С, ту же последовательность действий, что на шаге 6; полученные числа [p, Y₀], …, [p, Y_2t] поместить в стек V в порядке получения. Не забудьте удалить вершину стека С.

8. (Заполнение заново стека С.) Попеременно удалять (2t раз) вершины стеков V и U и помещать эти значения в стек С. В результате значения, вычисленные на шагах 6 и 7, будут помещены, чередуясь, в стек С в обратном порядке. После выполнения этого перемешивания верхняя часть стека С, рассматриваемая снизу вверх, будет иметь вид [р, Y_2t], [p, X_2t], …, [р, Y₀], [p, Х₀], на вершине будет [р, Х₀]. Поместить в управляющий стек один код операции интерполировать и 2t кодов операции сохранять и вернуться к шагу 4.

9. (Подготовка к интерполяции.) Присвоить к значение 0. Выбрать два верхних элемента стека С и поместить их в обычные переменные и и v. Оба числа и и v будут состоять из 32 битов. Используя некоторую другую подпрограмму умножения, вычислить [64, w] = [64, uv]. Это умножение можно выполнить аппаратно или с помощью подпрограммы, как вы найдете нужным.