► 18. [М24] Покажите, как расширить алгоритм L (как алгоритм А был расширен до алгоритма X) для решения уравнения (15) при больших и и v.

19. [21] Примените метод, описанный в разделе, для нахождения общего целочисленного решения следующих систем уравнений.

а) Зх--7у--11г = 1 Ь) 3x + 7y+llz= 1

5х -f 7i/ - 52 = 3 5х + 7у- 5z = -3

20. [М37] Пусть и и v - нечетные целые числа, независимо и равномерно распределенные в интервалах 2™ < и < 2""", 2" < и < 2""*". Чему равна точная вероятность того, что в алгоритме В за один цикл "вычитание и сдвиг" величины и и и уменьшатся до интервалов 2™ < U < 2™+!, 2 <v < 2"+1 (выражается как функция т, п, т и п)?

21. [НМ26] Пусть Стп и Dmn -Среднее число шагов вычитания и среднее число сдвигов при выполнении алгоритма В соответственно в случае, если числа и и к нечетны, [Ig uJ = m и [Ig uJ = п. Покажите, что при фиксированных п и m -> оо получаем значения Стп = im-1-0(1) и Dmn=m + 0{1).

22. Продолжая предыдущее упражнение, покажите, что если для некоторых постоянных Q, /3 и 7 выполняется Стп = ОШ + 0П + у, ТО

(N- m)iN - n)2"+"-C™„ = 2(ii(a + 0)N + 0(1)),

l<n<m<JV

(N- n)2"-C„„ = 2 (i(a + m + 0(1)).

l<n<n

► 23. [M20] Чему равна вероятность того, что после выполнения алгоритмом В п циклов "вычитание и сдвиг" будет выполняться неравенство v/u < х при условии, что выполнение алгоритма начинается с больших случайных целых чисел? (Здесь х - произвольное вещественное число > 0; не предполагается, что u>v.)

24. [М20] Предположим, что на шаге В6 и > и допустим, что отношение v/u имеет ограниченное распределение Брента G. Чему равна вероятность того, что при выполнении шага В6 в следующий раз будет и < v?

25. [Мй] Из уравнения (46) следует, что pi = -Л. Докажите, что р2 = Л/2.

26. [М22] Докажите, что если G(x) удовлетворяет уравнениям (36)-(40), то

2G(x) - ЪС(2х) -t- 2G(4x) = G(l -t- 2x) - 2G(1 -t- 4x) -t- 2G(1 -t- 1/x) - G(l -t- l/2x).

27. [M22] Докажите соотношение (58), которое выражает фп в обозначениях чисел Бернулли.

28. [НМ36] Исследуйте асимптотическое поведение п. Указание. См. упр. 6.3-34.

► 29. [НМ26] (Р. П. Брент (R. Р. Brent).) Найдите Gi (х) - распределение величины

min(u, v)/max(u, v)

в результате выполнения первого цикла "вычитание и сдвиг" алгоритма В согласно (35). Указание. Положите Sn+i(x) = 2~*Gn(l/(l -f 2x)) и примените к гармоническим

суммам преобразование Меллина [см. Р. Flajolet, X. Gourdon, P. Dumas, Theor. Сотр. Sci. 144 (1995), 3-58].

30. [HM39] Продолжая предыдущее упражнение, найдите G2(x).

31. [НМ46] Докажите или опровергните справедливость соотношения Балле (Vallee) (61).

32. [НМ47] Является ли единственной функция G(x), удовлетворяющая уравнениям (36) и (37)?

33. [М46] Исследуйте предложенный Харрисом (Harris) "бинарный алгоритм Евклида", сформулированный после программы В.

34. [НМ49] Докажите строго, что модель Брента описывает асимптотическое поведение алгоритма В.

35. [М23] Для любых неотрицательных целых чисел т,п > О рассмотрите ориентированный граф с вершинами (т, п) и дугами от вершин (т, п) к вершинам (т, п) для всех возможных циклов "вычитание и сдвиг" алгоритма В, чтобы преобразовать целые числа и и V, обладающие свойствами [IguJ = m и [IguJ = п, в целые числа и и v, обладающие свойствами [IguJ = m и [IgiJ = п . Существует также специальная вершина "Стоп" с дугой, соединяющей вершины (п, п), и "Стоп" для всех п > 0. Определите длину самого длинного участка пути от вершины (m,n) до вершины "Стоп". (Эта величина дает верхнюю границу максимального времени выполнения алгоритма В.)

► 36. [М28] Для m > п > 1 найдите такие значения ииь, обладающих свойствами [Ig uJ = m и [Ig dJ = n, чтобы для выполнения алгоритма В потребовалось т + 1 шагов вычитания.

37. [М32] Докажите, что число вычитаний на шаге В6 алгоритма В никогда не превысит величины 1 + [Ig шах(и, v)\.

* 38. [М32] (Р. В. Госпер (R. W. Gosper).) Покажите, как модифицировать алгоритм В для больших чисел с помощью идеи, аналогичной той, которая используется в алгоритме L.

► 39. [М28] (В. Р. Пратт (V. R. Pratt).) Распространите алгоритм В на алгоритм Y, который является аналогом алгоритма X.

► 40. [М25] (Р. П. Брент и X. Т. Кунг (Н. Т. Kung).) Излагаемый ниже вариант бинарного алгоритма лучше алгоритма В с точки зрения аппаратной реализации, так как он не требует проверки знака числа и - v. Допустим, что и нечетно; тогда числа и и v могут быть одновременно либо положительны, либо отрицательны.

К1. [Начальная установка.] Присвоить с +- 0. (Этот счетчик оценивает разность между lgu и lgi>.)

К2. [Выполнено?] Если и = О, то закончить алгоритм с результатом и.

КЗ. [Сделать v нечетным.] Присваивать v +- v/2 и с +- с -t-1 нуль или более раз до тех пор, пока v не станет нечетным.

К4. [Сделать с < 0.] Если О О, то заменить и v и присвоить с i--с.

К5. [Сократить.] Присвоить w {и + v)/2. Если w четно, присвоить v <г- w, в противном случае присвоить v -t- w - v и вернуться к шагу К2.

Докажите, что шаг К2 вьшолняется не более чем 2 -Ь 2 Ig max(u, ?;) раз.

41. [М22] При помощи алгоритма Евклида найдите простую формулу для

gcd(10" - 1, 10" - 1), где тип - неотрицательные целые числа.

42. [МЗО] Вычислите определитель

gcd(l,l) gcd(l,2) ... gcd(l,n) gcd(2,l) gcd(2,2) ... gcd(2,n)

gcd(n, 1) gcd(n,2) ... gcd(n,n)

М.5.З. Анализ алгоритма Евклида

Время выполнения алгоритма Евклида зависит от Т-количества выполненных шагов деления А2 (см. алгоритм 4.5.2А и программу 4.5.2А). Величина Т является также важным фактором, определяющим время выполнения других алгоритмов, например вычисление функций, удовлетворяющих закону обратимости (см. раздел 3.3.3). Мы увидим в этом разделе, что математический анализ величины Т интересен и поучителен.

Связь с цепными дробями. Алгоритм Евклида тесно связан с цепными (непрерывными) дробями, которые можно выразить в виде

ai -1- -

= Ьх1(а1+Ь21(а2+Ьз1(- /(пп-х+Ьп/ап) ...)))•

а2 +-- (1)

. Ьп ап-х + - an

Существует красивая теория цепных дробей, которой посвящен ряд классических книг, таких как О. Perron, Die Lehre von den Kettenbriichen, 3rd edition (Stuttgart: Teubner, 1954), 2 volumes; Хинчин A. Я. Цепные дроби.-М.-Л.: ГИТТЛ, 1949; Н. S. Wall, Analytic Theory of Continued Firactions (New York: Van Nostrand, 1948). С ранней историей развития теории цепных дробей можно ознакомиться в книге Claude Brezinski, History of Continued Fractions and Fade Approximants (Springer, 1991). Мы ограничимся сравнительно кратким изложением этой теории, рассматривая только те ее аспекты, которые необходимы для более глубокого пони.мания поведения алгоритма Евклида.

Первостепенный интерес для нас будут представлять только те цепные дроби, в которых все Ь в выражении (1) равны единице. Для удобства записи введем обозначение

ХиХ2,..., Хп = 1/ (Ж1 + 1/(Ж2 + 1/(- • • (Хп-Х + 1/Хп) ))) (2)

Тогда, к примеру,

/М = :, хх,х2 = =7tVt-

Xi Xi + 1/Х2 Х\Х2 + 1

Если п = о, символ xi,...,Xnl/ принимается равным нулю. Введем, кроме того, так называемые континуанты, гыи К-полиномы Kn(xi,X2, -iXn), от п переменных при п > О, задаваемые правилом

{1 при п = 0;

Xi при п = 1; (4)

XiKn-x(X2,---,Xn) + Kn-2(x3,---,Xn) ПрИ п > 1.

Таким образом, K2(xi,X2) = a;ia;2 + l, Кз(х1,Х2,хз) = ххХ2Хз+Х1+хз и т. д. В общем случае, как заметил Л. Эйлер в 18 веке, Кп(хх,Х2,. ,Хп)-сумма всех членов, получаемых, если, начиная с ХхХ2 .. .Хп, вычеркивать нуль или более неперекрывающихся пар соседних переменных XjXj+Xi количество таких членов равно Fn+x-