Эта теорема явилась первым практическим применением последовательности чисел Фибоначчи. С тех пор числа Фибоначчи нашли широкое применение при выполнении и исследовании алгоритмов. Следующий результат получил Т. Ф. де Ланьи (Т. F. de Lagny) [Mem. Acad. Sci. Paris 11 (1733), 363-364]. Он составил таблицы нескольких первых /С-полиномов и обнаружил, что числа Фибоначчи дают для цепных дробей заданной длины наименьшие числитель и знаменатель. Однако он совсем не имел в виду вычисление наибольшего общего делителя. Первым на связь между числами Фибоначчи и алгоритмом Евклида указал Э. Леже (Е. Leger) [Correspondance Math, et Physique 9 (1837), 483-485].

Вскоре после этого П. Ж. Е. Финк (Р. J. Ё. Finck) [Traite Elementaire dArith-metique (Strasbourg, 1841), 44] другим методом доказал, что если и > t; > О, то gcd(u,i;) вычисляется не более чем за (21gw+l) шагов, а Г. Ламе (G. Lame) [Comptes Rendus Acad. Sci. Paris 19 (1844), 867-870] распространил полученный результат на 5[log2o(i -I-1)1. Полное изложение этих первых работ по анализу алгоритмов появилось в интересном обзоре Дж. О. Шэллита (J. О. Shallit) Historia Mathematica 21 (1994), 401-419. Однако более точная оценка наихудшего случая является прямым следствием теоремы F.

Следствие L. Если О < t; < iV, то число шагов деления, необходимых алгоритму 4.5.2А для выполнения операций с числами и и t;, не превышает [log (3 - ф)М\.

Доказательство. После выполнения шага А1 имеем v > и mod v. Поэтому согласно теореме F максимальное число шагов п имеет место в том случае, когда v = F„+i и umodt; = F„. Так как F„+i < N, то ф"+/у/Ь < N (см. 1.2.8-(15)). Следовательно, <{V5/ф)N = {3-ф)М. I

Величина log (3 - ф)М приближенно равна 2.078 In 7V + .6723 « 4.785 logjo N + .6723. По поводу обобщений теоремы F обратитесь к упр. 31, 36 и 38.

Приближенная модель. Теперь, когда известно максимально возможное количество шагов деления, попытаемся найти их среднее число. Пусть Т{т,п) - число шагов деления в случае, когда алгоритм Евклида имеет на входе и = т и v = п. Тогда

Г(т,0) = 0; T{m,n) = l + T{n,mmodn) при п > 1. (18)

Пусть Т„ - среднее число шагов деления, когда v = п, а и выбирается случайным образом. Поскольку после выполнения первого шага деления на ход выполнения алгоритма влияет только значение и mod v, можно записать

"0<fc<n

Например, Г(0,5) = 1, Т(1,5) = 2, Т(2,5) = 3, Г(3,5) = 4, Г(4,5) = 3, так что

Ts = 1(1 + 2 + 3 + 4 + 3) = 2.

Задача состоит в оценке Т„ при больших значениях п. Попробуем сначала применить приближение, предложенное Р. У. Флойдом (R. W. Floyd). Можно предположить, что для О < А; < п значение п, по существу, "случайно" по модулю к, так что можно записать

r„«l + -(To + Ti + --- + r„ i).

Тогда Тп « S„, где последовательность (5„) есть решение рекуррентного соотношения

5о = 0, Sn = l + -{So + Si + --- + S„-i), п>1. (20)

Это рекуррентное соотношение легко решить, если учесть, что Sn+i = 1 -f- -4т (5о + 5i + • • • + Sn-i + Sn)

71 "Г 1

Следовательно, 5„ равно 1 + + + = Нп - гармоническому числу. Теперь приближение Г„ и 5„ дает Т„ т \пп + 0{1).

Сравнение этого приближения с таблицами истинных значений Г„ показывает, однако, что Inn - это слишком много. (Тп возрастает не так быстро.) Предположение, что число п случайно по модулю fc, является по этой причине слишком пессимистическим. И в самом деле, более вни.мательный анализ показывает, что среднее значение числа п mod к меньше среднего значения числа к при 1 < fc < п:

- (nmodfc) = i Y1 {n-qk)[[n/{q + l)\ <k<[n/q\

="-s,£((""Г)-(""V))

1<Я<п

= (l-)n + 0(logn) (21)

(см. упр. 4.5.2-10(с)). Это равно примерно .1775п, а не .25п. Поэтому значение п mod fc меньше значений, предсказываемых моделью Флойда, а алгоритм Евклида выполняется быстрее, чем предсказывает приближенная модель.

Непрерывная модель. При v = N поведение алгоритма Евклида, по существу, определяется поведением правильной цепной дроби для X = 0/N, 1/N ... ..., (N - 1)/N. При очень больших Л естественно рассматривать разложение числа X в правильную цепную дробь фактически как случайного вещественного числа, равномерно распределенного в интервале [О.. 1). Рассмотрим функцию распределения

Fn{x) = Рт{Хп <х) при О < ж < 1 (22)

равномерно распределенного числа X = Xq- По определению правильных цепных дробей получаем Fo{x) = х и

Fn+i (х) = J2 < 1/Хп <к + х)

= £Рг{1/{к + х)<Хп<1/к)

к>1

= J2iFn{l/k)-Fn{l/{k + x))). (23)

*>1

Если распределения Fo(x),Fi{x),..., определяемые этими формулами, сходятся к предельному распределению Fck,{x) = F{x), то получаем

F{x) = £ini/k)-F{l/{k + x))). (24)

(Аналогичное соотношение, 4.5.2-(36), было получено при рассмотрении бинарных алгоритмов определения наибольшего общего делителя.) При любом основании 6 > 1 одна из функций, удовлетворяющих уравнению (24), имеет вид F{x) = Iog(,(l + х) (см. упр. 19). Из дополнительного условия F{1) = 1 следует, что 6=2. Таким образом, вполне обосновано предположение, что F{x) = lg(l + х) и что последовательность Fn{x) сходится к этому пределу.

Можно было бы предположить, например, что jF() = lg() ~ 0.58496. Посмотрим, насколько близко F„(i) к этому значению при малых п. Имеем Foi) - 0.50000 и

Fx{\) = Я1/2 = 2 - 21п2 « 0.61371;

*>1

= Hi/2

Fi) = Н2/2 - Н2/3 + Щ/* - Н2/5 + Н2/6 - Н2/7 Н----

(см. табл. 3 приложения А). Обобщение на степенной ряд

Я. = а2)х - ф)х 4- а)х - С(5)ж + • • • (25)

позволяет определить численное значение

F2{\) = 0.5765593276999140841882618721222705592452- . (26)

Получаем значение, близкое к 0.58496. Но совсем не очевидно, как получить хорошую оценку F„(i) при п = 3, т. е. при значении, меньшем, чем те значения, которые считаются действительно большими.

Впервые распределения F„(a;) были исследованы К. Ф. Гауссом (С. F. Gauss), который начал решать эту проблему 5 февраля 1799 года. В его записях за 1800 год перечислены различные рекуррентные соотношения и приведена краткая таблица значений, включающая (неточные) приближения для 2(5) ~ 0.5748. После завершения этих вычислений Гаусс записал: "Таш complicatae evadunt, ut nulla spes superesse videatur", т. e. "Они получаются такими сложными, что, кажется, нет никакой надежды". Двенадцать лет спустя Гаусс написал письмо Лапласу, в