Этюды для программистов

10. (Интерполяция при необходимости.) Выбрать вершину управляющего стека в переменную А. Если значение А есть интерполировать, то выполнить шаги с 11-го по 16-й, в противном случае перейти к шагу 17,

11. (Организация интерполяции.) Поместить [m, w] в стек W (это может быть значение, полученное на шаге 9 или 16). Присвоить s значение q_k, t — значение r_k, р — значение q_k?1 + q_k. Обозначим верхнюю часть стека W, рассматриваемую снизу вверх, как

[2р, Z₀], [2p, Z₁], …, [2р, Z_2t?1], [2p, Z_2t],

последнее из этих значений — на вершине стека.

12. (Внешний цикл деления Z.) Выполнять шаг 13 для i = 1, 2, …, 2t.

13. (Внутренний цикл деления Z.) Присвоить [2p, Z_j] значение ([2р, Z_j] ? [2р, Z_j?1])/i для j=2t, 2t ? 1, …, i + 1, i. Все разности будут положительными, а все деления выполняются нацело, т. е. без остатка.

14. (Внешний цикл умножения Z.) Выполнять шаг 15 для i = 2t ? 1, 2t ? 2, …, 2, 1.

15. (Внутренний цикл умножения Z.) Заменить [2р, Z_j] на [2p, Z_j] ? i[2p, Z_j+1] для j = i, i + 1, …, 2t ? 2, 2t ? 1. Все разности будут положительными, и все результаты поместятся в 2р битов.

16. (Образование нового w и начало нового цикла.) Присвоить значение многочлена

(… ([2р, Z_2t]2^s + [2p, Z_2t?1]2^s + … + [2p, Z_i]2^s + [2p, Z₀]

переменной [2(q_k + q_k+1), w]. Этот шаг можно выполнять, используя только сдвиги и сложения длинных чисел. Заметьте, что используется та же переменная [m, w], что и на шаге 9. Удалить [2р, Z_2t], …, [2p, Z₀] из стека W. Присвоить k значение k + 1 и вернуться к шагу 10.

17. (Проверка окончания.) Если А имеет значение стоп, то в переменной [m, w], уже вычисленной на шаге 9 или 16, находится результат алгоритма. В этом случае окончить работу.

18. (Сохранение значения.) Значением А должен быть код сохранить (если это не так, завершить алгоритм по ошибке). Присвоить k значение k + 1 и поместить [q_k + q_k?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; число в колонке n_k равно наибольшему числу битов, которое может быть обработано алгоритмом при K = k. Очевидно, что предельное значение 10 для K не является очень серьезным ограничением. При желании этот предел можно повысить.

Таблица 22.1. Значения q, r и n
k	qk	rk	nk
0	16	4
1	16	4	32
2	64	4	80