Обозначив левую часть (15) через {1/к\) W{x), замечаем, что

\*-W(x)

к \{к-1)Г " {к-1)\

и (l/Zc!) А* И(0) = аи- Таким образом, коэффициенты Oj можно вычислить при помощи очень простого метода, который иллюстрируется здесь на примере полинома W{x), определенного соотношениями (13).

304 1382/2 = 691

1980 3428/2= 1714 I 144/4= 36 (16)

084 J:. 6338/2 = 3169

18526

Крайняя слева колонка этой таблицы состоит из заданных значений W(0), W(l),... ..., Vr(4). Чтобы вычислить элементы в k-Vi колонке, нужно найти разность между соседними элементами предыдущей колонки и разделить эти разности на к. Коэффициенты Oj -это верхние числа в колонках, так что ао = 10, Oi = 294, ..., 04 = 36; отсюда имеем

W{x) = Збх* + 341x3 + 691x2 + 294 + 10

= (((36(х - 3) + 341)(х - 2) + 691)(х - 1) + 294)а; + 10. (17)

В общем случае можно записать

W{x) = (... ((om-i(х - m -f 2) + ат-2){х - m + 3) + am-z){x - m + 4) + • • • + Oj)x + ао.

Данная формула показьшает, каким образом с помощью коэффициентов a„i можно вычислить коэффициенты Wm-i,..., Wi, Wo-

(18)

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

am i(x-m + 2) + am 2,

(am i(x - m + 2) + am 2)(x - m + 3) + а-г и т. д. Согласно данной таблице имеем

W{x) = Збх" + 125х -Ь 64x2 + 69х + 10, (19)

так что ответом будет 1234 • 2341 = W{16) = 2888794, где W{16) вычисляется с помощью операций сложения и сдвига. В разделе 4.6.4 рассмотрено обобщение этого метода вычисления коэффициентов.

Из основного тождества для чисел Стирлинга (см. упр. 1.2.6-(45)),

видно, что, если коэффициенты полинома W{x) неотрицательны, таковыми же будут и числа ttj. В этом случае все промежуточные результаты в вышеприведенных вычислениях неотрицательны. Данное обстоятельство еще больше упрощает алгоритм умножения Тоома-Кука, который теперь будет рассмотрен подробно. (Нетерпеливые читатели могут перелистать страницы подраздела С.)

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

Стеки и, V Временное хранение (7(j) и V{j) на шаге Т4 Стек С Сомножители и управляющие коды

Стек W Сохранение величин W{j)

Эти стеки могут содержать либо двоичные числа, либо специальные управляющие символы, называемые "код-1", "код-2" и "код-3". Алгоритм формирует также дополнительную таблицу чисел qk, Гк, построенную таким образом, что ее можно хранить в запоминающем устройстве как линейный список, единственный указатель которого, перемещающийся по списку в обоих направлениях, может использоваться для выбора нужного текущего элемента из этого списка.

(Стеки С hW используются для контроля рекуррентного механизма алгоритма умножения довольно простым способом, который является частным случаем общей процедуры, рассматриваемой в главе 8.)

Т1. [Вычислить таблицы q,r.] Очистить стеки U,V, С и W и присвоить

к-(~ 1, qo <~ qi Го <- Г1 <- 4, <Э <- 4, Д <- 2.

Если теперь qk-i +qk <п, присвоить

к+-к + 1, Q+-Q + R, qk<2, Гк<-2

и повторять эту операцию до тех пор, пока не выполнится условие qk-i+qk > тг. [Примечание. Для вычисления R <- [VQ \ нет необходимости в извлечении корня квадратного, так как при {R + 1) < <5 можно просто присвоить i? Л + 1, а если (R+l) > Q, то нужно оставить R неизменным (см. упр. 2). На этом шаге строятся такие последовательности.

ТЗ. Проверить уровень рекурсии

код-3

Т7. Найти все а

Найти все W{j)

(-> Сформировать ответ

Т10. Возвратиться

код-2

код-1

Рис. 8. Алгоритм Тоома-Кука умножения с высокой точностью.

При умножении 70 ООО-битовых чисел этот шаг закончился бы при значении А; = 6, так как 70000 < 2 + 2.)

Т2. [Занести u,v в стек.] Занести "код-1" в стек с, затем поместить и и г; в стек с как числа, каждое из которых содержит ровно qk-i + Як бит.

ТЗ. [Проверить уровень рекурсии.] Уменьшить А; на 1. Если А; = О, то в вершине стека с находится в данный момент два 32-битовых числа и и v. Извлечь из стека эти числа, присвоить w <- uv, пользуясь встроенной программой для умножения 32-битовых чисел, и перейти к шагу Т10. Если А; > О, то присвоить г <- Гк, q <- Як, Р <- Як-1 + 9* и перейти к шагу Т4.

Т4. [Разбить на г -Ь 1 частей.] Число, находящееся в вершине стека с, будем рассматривать как список из г -Ы чисел, каждое из которых состоит из я бит, {Ur . ..UiUo)24- (В вершине стека с находится (г -Ь \)я = {Як + дй+1)-битовое число.) Для J = 0,1,..., 2г вычислим р-битовые числа

(... {Urj + Ur-i)j + + Ui)j + Uo = U{j)

и поместим эти значения в стек U. (На самом дне стека U сейчас находится и{0), затем следует U{1) и т. д., а на вершине стека - U{2r). Согласно упр. 3 имеем

U{j) < U{2r) < 2»((2r) + (2r)-i + • • + 1) < 2«+i(2r)- < 2".)

Далее извлекаем из стека с значения Ur - UiUq.

Теперь на вершине стека с находится другой список г+1 д-битовых чисел Vr .. .ViVq, а р-битовые числа

(... {Vrj + Vr-i)j + + Vi)j + Vo = V{j)

таким же образом должны быть помещены в стек V. После завершения этих действий переместить из стека с числа Vr .. .ViVq.