14. (Внешний цикл умножения Z.) Выполнять шаг 15 для i = 2t − 1, 2t − 2, …, 2, 1.
15. (Внутренний цикл умножения Z.) Заменить [2р, Zj] на [2p, Zj] − i[2p, Zj+1] для j = i, i + 1, …, 2t − 2, 2t − 1. Все разности будут положительными, и все результаты поместятся в 2р битов.
16. (Образование нового w и начало нового цикла.) Присвоить значение многочлена
(… ([2р, Z2t]2s + [2p, Z2t−1]2s + … + [2p, Zi]2s + [2p, Z0]
переменной [2(qk + qk+1), w]. Этот шаг можно выполнять, используя только сдвиги и сложения длинных чисел. Заметьте, что используется та же переменная [m, w], что и на шаге 9. Удалить [2р, Z2t], …, [2p, Z0] из стека W. Присвоить k значение k + 1 и вернуться к шагу 10.
17. (Проверка окончания.) Если А имеет значение стоп, то в переменной [m, w], уже вычисленной на шаге 9 или 16, находится результат алгоритма. В этом случае окончить работу.
18. (Сохранение значения.) Значением А должен быть код сохранить (если это не так, завершить алгоритм по ошибке). Присвоить k значение k + 1 и поместить [qk + qk−1, w] в стек W. Это значение w, только что вычисленное на шаге 9 или 16. Теперь вернуться к шагу 3.
Мы почти не обосновывали и не объясняли алгоритм; вам придется кое в чем поверить на слово. Причина отсутствия объяснений кроется в том, что они крайне длинны и математичны, и у нас просто не хватило бы места. Изложение алгоритма в большой степени опирается на монографию Кнута; если вы хотите ознакомиться с алгоритмом подробнее, обратитесь к этой книге. Мы все же дадим некоторые комментарии, возможно способствующие лучшему пониманию.
1. (Структура алгоритма.) Наша версия алгоритма отличается от описанной у Кнута в основном структурой циклов. На рис. 22.1 представлена общая схема верхнего уровня алгоритма Тоома—Кука[32].
begin
long integer [n, u], [n, v];
integer K, Q, R, q [0: 10], r [0: 10];
long integer stack C, U, V, W;
control stack code;
integer k, p, s, t, i, j;
long integer X, Y, Z, w;
control A;
Шаг 1;
Шаг 2;
while code не пуст do
while k > 1 do
шаг 5; шаг 6; шаг 7; шаг 8;
end;
шаг 9;
pop code into A; while А = интерполировать do
шаг 11;
for i=1 to 2t do шаг 13;
for i=2t − 1 downto 1 do шаг 15;
шаг 16;
end;
if A = стоп then return [m, w];
if A = сохранить then шаг 18; else abort;
end; * главного цикла *
end; * алгоритма Тоома—Кука *
Рисунок 22.1. Управляющая схема алгоритма Тоома—Кука.
2. (Таблицы размеров.) Значения массивов, вычисленные на шаге 2, показаны в табл. 22.1; число в колонке nk равно наибольшему числу битов, которое может быть обработано алгоритмом при K = k. Очевидно, что предельное значение 10 для K не является очень серьезным ограничением. При желании этот предел можно повысить.
| Таблица 22.1. Значения q, r и n | |||
| k | qk | rk | nk |
| 0 | 16 | 4 | |
| 1 | 16 | 4 | 32 |
| 2 | 64 | 4 | 80 |
| 3 | 256 | 4 | 320 |
| 4 | 1024 | 8 | 1280 |
| 5 | 8192 | 8 | 9216 |
| 6 | 65536 | 16 | 73728 |
| 7 | 1048576 | 16 | 1114112 |
| 8 | 16777216 | 16 | 17825792 |
| 9 | 268435456 | 32 | 285212672 |
| 10 | 8589934592 | 32 | 8858370038 |
3. (Глубина стеков в первом цикле.) Максимальная глубина стеков U и V на шагах с 5-го по 8-й равна 2(rK−1 + 1). Глубина стека С может возрастать до 
.
4. (Глубина стеков во втором цикле.) Общая глубина стека W может достигать 
. Управляющий стек может достигать глубины 
. На шагах 14, 15 и 16 верхняя часть стека W используется как массив. Этот массив может содержать максимум 2rk−1 + 2 элементов.
5. (Размер исходных данных.) Для любого числа битов n в диапазоне ni−1 + 1 ≤ n ≤ ni алгоритм Тоома—Кука требует одинакового времени вычислений. Таким образом, сложность вычислений весьма негладко зависит от размера исходных данных. Поэтому при выполнении длинных вычислений имеет смысл подбирать число битов вблизи верхнего конца одного из диапазонов для n. Учитывайте, что для представления одной десятичной цифры требуется примерно 3⅓ бита.
32
Дадим небольшое пояснение к рисунку: long — длинный, stack — стек, control — управляющий pop … into — удалить вершину … и поместить в, abort — аварийное окончание. Остальные ключевые слова имеют тот же смысл, что в яэыке Паскаль. —