к u/v, причем

u/v < u/v < u"/v". (27)

Отношение u/v определяет последовательность частных, полученных в алгоритме Евклида. Если алгоритм Евклида одновременно выполнять над значениями (и, v) и (и", v") с однократной точностью до тех пор, пока не получим различные частные, то будет нетрудно заметить, что такая же последовательность частных получится, если выполнять алгоритм над числами (и, и) с многократной точностью. Итак, посмотрим, что произойдет, когда алгоритм Евклида применить к (и, v) и к (и", v").

Пять первых частных одинаковы в обоих случаях, так что они должны быть правильными. Но на шестом шаге обнаруживается, что q ф q", поэтому вычисления с однократной точностью прекращаются. Тем самым мы выяснили, что если бы вычисления выполнялись с исходными числами как с числами многократной точности, то это происходило бы так.

(28)

(Следующее частное находится между 3 и 19.) Независимо от количества разрядов чисел U и и до тех пор, пока выполняется (27), первые пять шагов алгоритма Евклида будут такими же, как в (28). Поэтому вычисления с однократной точностью можно выполнять на первых пяти шагах, а операции с многократной точностью - только при вычислении значений -Ащ + lluo и Тщ - l9vo- В этом случае получаем и = 1268728, V = 279726; дальнейшие вычисления можно продолжить подобным же образом с числами и = 1268, v = 280, и" = 1269, v" = 279 и т. д. При наличии большего накопителя можно было бы увеличить количество шагов, на которых вычисления выполняются с однократной точностью. Из примера видно, что в один сложный шаг объединяются только пять циклов алгоритма Евклида, а если бы, скажем, размер слова равнялся десяти разрядам, можно было бы объединить в один шаг до двенадцати циклов. Из результатов, доказанных в разделе 4.5.3, следует, что на каждой итерации число циклов с многократной точностью, которые можно заменить циклами с однократной точностью, пропорционально размеру слова, используемому в вычислениях с однократной точностью.

Метод Лемера можно сформулировать следующим образом.

Алгоритм L (Алгоритм Евклида для больших чисел). Пусть и и v - представляемые с однократной точностью неотрицательные целые числа, такие, что и > v. Этот алгоритм вычисляет наибольший общий делитель чисел и и v, используя вспомогательные р-разрядные переменные и, v, А, В, С, D, Т, q, которые представлены с однократной точностью, и вспомогательные переменные taw, которые представлены с многократной точностью.

L1. [Начальная установка.] Если число v достаточно мало, чтобы быть представленным в формате с однократной точностью, то gcd(u, v) вычисляется по алгоритму А, и на этом вычисления заканчиваются. В противном случае обозначим р ведущих разрядов числа и через й, а соответствующие разряды числа v - через v. Другими словами, если используется представление чисел в системе счисления по основанию Ь, то й •«- [u/b*J и г) •«- [w/b*J, где к - наименьшее возможное число, удовлетворяющее условию и < Ь.

Присвоить А <- I, В О, С <- О, D I. (Эти переменные представляют коэффициенты в (28), где

и = Аио + BvQ и w = Cuq ¥ Dvq (29)

в равносильных операциях алгоритма А над числами с многократной точностью. Кроме того,

ий + В, v = v + D, и" = й + А, v" = v + C (30)

в обозначениях рассмотренного выше примера.) L2. [Проверить частное.] Присвоить q*- [(u+A)/(v+C)]. Если q: [{u+B)/(v+D)\, то перейти к шагу L4. (На этом шаге проверяется выполнение условия q ф д" в обозначениях того же примера. В процессе вычислений на этом шаге при некоторых обстоятельствах, когда и - V-\vi.A- \ или когда v - - \ и D = 1, может возникнуть переполнение при вьшолнении операций в формате с однократной точностью. В силу равенств (30) всегда будут выполняться условия

О < й -t- Л < Ь", О < г) -t- С < Ь",

0<й-)-В<Ь, 0<г} + £)<Ь.

Может оказаться, что выполнится одно из равенств г)-)-С = 0игЯ-£> = 0, но не оба одновременно. Поэтому попытка деления на нуль на этом шаге означает "Перейти непосредственно к шагу L4".)

L3. [Имитация алгоритма Евклида.] Присвоить Т +- А - qC, А +- С, С +- Т, Т В - qD, B+-D, D<-T, T+-u-qv, u-i-v, vi-Tii возвратиться к шагу L2. (Эти вычисления с однократной точностью равносильны операция.м с многократной точностью в процедуре (28) с учетом (29).)

L4. [Шаг, на котором выполняются вычисления с многократной точностью.] Ести В = О, то, используя деление с многократной точностью, присвоить t <- и mod v, и +- v, v +- t. (Это может случиться только тогда, когда с помощью операции с однократной точностью нельзя моделировать операцию с многократной точностью. Отсюда следует, что алгоритму Евклида требуется очень большое частное, что может произойти крайне редко.) В противном случае присвоить t •«- Аи, t <- t + Bv, w <- Си, w <- w + Dv, и <- t, v +- w (вьшолняя непосредственно операции с многократной точностью). Возвратиться к шагу L1.

с учетом неравенств (31) в процессе вычислений значения величин А, В, С, D представляются с однократной точностью.

Для реапизации алгоритма L требуется несколько более сложная программа, чем для алгоритма В, но при оперировании большими числами этот алгоритм на многих компьютерах вьшолняется быстрее. Подобным образом можно ускорить выполнение бинарного алгоритма В в завершающей стадии (см. упр. 38). Преимущество алгоритма L заключается в следующем: он определяет последовательность частных, получаемых при выполнении алгоритма Евклида, что используется в многочисленных приложениях (см., например, упр. 43, 47, 49, упр. 51 в разделе 4.5.3, а также упр. 4.5.3-46).

*Анализ бинарного алгоритма. В заключение этого раздела для обоснования установленных ранее формул проанализируем время выполнения алгоритма В.

Выясняется, что точно описать поведение алгоритма В крайне затруднительно, но можно начать анализ этого алгоритма с его приближенной модели. Предположим, что числа и и V нечетны, и > v и

[lguj=m, [\gv]=n. (32)

(Таким образом, и является (т-)- 1)-битовым числом, av - (n-t- 1)-битовым числом.) Рассмотрим выполнение в алгоритме В цикла "вычитание и сдвиг", т. е. операцию, которая начинается на шаге В6, а прекращается после окончания выполнения шага В5. Каждый цикл "вычитание и сдвиг" при и > v вычисляет разность и - v и сдвигает эту величину вправо до тех пор, пока не будет получено нечетное число и, которое замещает число и. Если входные числа случайны, можно ожидать, что примерно в половине случаев и - (и - v)/2, примерно в четверти случаев и = (и - w)/4, примерно в одной восьмой случаев и = (и - w)/8 и т. д. Получаем

[\gu\==m-k-r, (33)

где к - число разрядов, на которые было сдвинуто вправо число и - v, а г есть [Ig uJ - [lg(u - v)\ - количество битов, потерянных слева во время вычитания числа V из числа и. Заметим, что г < 1 при т>п + 2, аг>1 при т = п.

Взаимосвязь между к иг довольно беспорядочная (см. упр. 20), однако Ричард Брент (Richard Brent) нашел изящный способ анализа поведения приближенной модели алгоритма, положив и и v достаточно большими, такими, чтобы отношение v/u имело непрерывное распределение при дискретном изменении А;. [См. Algorithms and Complexity, edited by J. F. Traub (New York: Academic Press, 1976), 321-355.] Предположим, что и и v - большие целые числа, возможно, случайные, но обязательно нечетные и их отношение подчинено определенному закону распределения. Тогда на шаге В6 младшие значащие биты величины t = и - v могут быть случайными, но величина t будет четной. Следовательно, t будет нечетно кратным 2* с вероятностью 2"*; это приближенная вероятность того, что в цикле "вычитание и сдвиг" потребуется выполнить А; сдвигов вправо. Другими словами, получено подходящее приближение, описывающее поведение алгоритма В при сделанных предположениях о том, что переход от шага В4 к шагу ВЗ всегда будет происходить с вероятностью 1/2.

Пусть Gn{x) - вероятность того, что mm{u,v)/max{u,v) будет >х после выполнения с учетом этих предположений п циклов "вычитание и сдвиг". Если и > v