Можно также оценить среднее количество шагов деления в случае, когда оба числа и и V равномерно распределены в интервале между 1 и Л, вычислив

(57)

в предположении справедливости формулы (55) в упр. 29 показано, что эта сумма имеет вид

lnN + 0(l), (58)

а эмпирические расчеты, выполненные с теми же числами, которые использовались при выводе соотношения 4.5.2-(65), хорошо согласуются с формулой

ln7V + 0.06. (59)

Конечно, пока мы ничего не доказали о поведении Г„ и г„ в общем случае. До сих пор рассматривались только возможные обстоятельства, при которых должны быть верны определенные формулы. К счастью, сейчас уже можно применить методику строгого доказательства, которая основана на тщательном анализе, выполненном рядом математиков.

Впервые главный член (121п2)/7г в формулах, приведенных выше, был получен независимо Джоном Д. Диксоном (John D. Dixon) и Гансом А. Хайльбронном (Hans А. Heilbronn). Диксон [J. Number Theory 2 (1970), 414-422] развил теорию распределений F„(a;), чтобы показать, что индивидуальные частичные отношения являются в определенном смысле независимыми одно от другого, и доказал, что для любого положительного е вьшолняется соотношение \Т{т,п)- ((121п2)/7г) 1пп < (lnn)/+% но не для значений тип exp(-c(e)(logЛ)/)Л в интервале 1 < m < п < N, где с(е) > 0. Совсем иной подход к этой проблеме, при котором вместо непрерывных переменных рассматриваются только целые числа, предложил Хайльбронн. В основу его идеи, излагаемой в несколько модифицированном виде в упр. 33 и 34, положен тот факт, что величину г„ можно определенным образом связать с числом способов представления п. Кроме того, в его работе Number Theory and Analysis, edited by Paul Turin (New York: Plenum, 1969), 87-96, показано, что распределение индивидуальных частичных отношений 1,2,..., которое рассматривалось выше, в действительности применимо ко всему множеству частичных отношений, принадлежащих дробям с заданным знаменателем. Это более точная форма теоремы Е. Через несколько лет Дж. В. Портер (J. W. Porter) [Mathematika 22 (1975), 20-28] получил еще более точный результат. Он установил, что

121п2.

lnn + C-(-0(n-i/«+), (60)

где С к, 1.4670780794 есть постоянная

(31n2 + 47- 247r-V(2)-2)-i; (61)

см. D. Е. Knuth, Computers and Math, with Applic. 2 (1976), 137-139. Таким образом, утверждение (50) полностью доказано. Используя формулу (60), Грэхэм X. Нортон

(Graham Н. Norton) [J. Symbolic Computation 10 (1990), 53-58] продолжил вычисления упр. 29, чтобы доказать, что эмпирическая константа 0.06 в формуле (59) в действительности равна

(3 In 2 + 47 - 127Г-2С(2) - 3) - 1 « 0.06535 14259.... (62)

Г. Э. Коллинз (G. Е. Colhns), применив классические алгоритмы выполнения арифметических операций, показал в SICOMP 3 (1974), 1-10, что среднее время выполнения алгоритма Евклида при оперировании числами многократной точности равно

(1 -I- log{max{u,v)/gcd{u,v))) logmin(M, tj). (63)

Резюме. Мы обнаружили, что наихудший случай алгоритма Евклида имеет место, когда входные числа и и v связаны с числами Фибоначчи (теорема F), а число шагов деления при О <v < N никогда не превышает величины [4.8 log N - 0.32]. Мы определили частоту появления различных частичных отношений, показав, к примеру, что приблизительно в 41% случаев на шаге деления получается [u/v\ = 1 (теорема Е). Наконец, в теоремах Хайльбронна и Портера доказывается, что среднее число Тп шагов деления при v = п приблизительно равно

((12 In 2)/тг) In п « 1.9405 logjo п,

если не учитывать корректирующий член, основанный на делителях числа п, как следует из уравнения (55).

УПРАЖНЕНИЯ

► 1. [20] Так как частное [u/v] равно единице более чем в 40% времени выполнения алгоритма 4.5.2А, на некоторых компьютерах может оказаться выгодным проверить этот случай и запретить выполнение операции деления, когда частное равно единице. Является ли следующая MIX-программа, реализующая алгоритм Евклида, более эффективной, чем программа 4.5.2А?

LDX JMP 1Н STX SUB CMPA

2F V V V

V <-гА

(- и. •гХ

i- и - V.

SRAX 5 гАХ <- гА.

JL 2F U-V <v?

DIV V rX +- гАХ mod v.

2Н LDA V гА <- и.

JXNZ IB Выполнено, если rX = 0.

2. [M2i] Вычислите произведение матриц

fxi 1\ (Х2 л (Хп \\

3. [M2i] Чему равен определитель

4. [М20] Докажите тождество (8).

5. [НМ25] Пусть xi, Х2, . . - последовательность вещественных чисел и каждое из них больще некоторого положительного числа б. Докажите, что существует бесконечная цепная дробь xi ,Х2,-- = Ит„-юо xi,.. .,Хп - Покажите также, что xi, xj,.. • необязательно существует, если предположить только, что Xj > О для всех j.

6. [М23] Докажите, что разложение числа в правильную цепную дробь единственно в следующем смысле. Если В\, В2, - положительные целые числа, то бесконечная цепная дробь JlB\, В2, .. есть иррациональное число А, расположенное между О и 1, разложение которого в правильную цепную дробь имеет элементы А„ = Вп для всех п > 1. Если же Bi, Вт -положительные целые числа, причем Вт > 1, то правильная цепная дробь для числа X = jjB\ВтЦ имеет элементы An = Вп для 1 < п < т.

7. [М26] Найдите все перестановки р(1)р(2)... р{п) целых чисел {1, 2,..., п}, таких, что Лп(х1,Х2, ...,Хп) = Лп(хр(1),Хр(2),... ,Хр(„)) является тождеством для всех xi, хг, ..., х„.

8. [M.2f] Покажите, что если при разложении в правильную цепную дробь числа X определено А„, то -1/А„ = А„,..., Ai, -ХЦ.

9. [М21] Покажите, что цепные дроби удовлетворяют следующим тождествам:

a) xi,...,x„ = xi,...,Xfc+ xfc+i,...,x„ , l<fe<n;

b) 0,xi,X2,...,x„ = xi-- х2,...,х„ , п>1;

c) Xl,. . .,-Xfc l,Xfc,0,Xfc+i,Xfc+2,...,X„ = Xl,.. .,Xfc l,Xfc --Xfc+l,Xfc+2,.. .,x„ , 1<К<п;

d) 1 - X1,X2,...,X„ = l,Xl - 1,X2,...,X„ , n > 1.

10. [M28] Из результата упр. 6 следует, что любое иррациональное число X единственным образом разложимо в правильную цепную дробь вида

А = Ао + А1,А2,Аз,... ,

где Ао - целое число и Ai, А2, A3, ... - положительные целые числа. Покажите, что если X имеет такое представление, то разложение числа 1/А в правильную цепную дробь имеет вид

1/А = Во + l/Bi,.. .,Вт,А,,Аб,...

для соответствующих целых чисел Во, Bi, Вт- (Наиболее интересен, безусловно, случай, когда Ао < 0.) Объясните, как можно выразить все В через Ао, Ai, А2, A3 и А4.

11. [МЗО] (Ж.-А. Серре (J.-A. Serret), 1850.) Пусть А = Ао-I- Ai, Аг, Аз, А4,... и Y = Во + Bi,B2, Вз, Bi,... II - представления в виде правильных цепных дробей двух вещественных -чисел А и У в смысле упр. 10. Покажите, что эти представления "эвентуально согласованы" в том смысле, что Ат+к = Вп+к для некоторых m и п и для всех fe > О тогда и только тогда, когда для некоторых целых чисел q, г, s, t выполняется X - {qY + r)/{sY+t) при \qt - rs\ = 1. (Эта теорема является аналогом представлений цепными дробями простого результата, заключающегося в том, что представления целых чисел А и У в десятичной системе счисления в конечном счете совпадают тогда и только тогда, когда для некоторых целых чисел q, г и s выполняется равенство X = (10У -I- г)/10*.)

► 12. [M5f] Квадратичной иррациональностью называют число вида (у/В - U)IV, где D, и и V - целые числа, удовлетворяющие условиям D > О, V О, и D не есть полный квадрат. Без потери общности можно предположить, что V является делителем числа D - , в противном случае это число можно переписать в виде {s/DV - U\V\)j{V\V\).

а) Докажите, что разложение в правильную цепную дробь (в смысле упр. 10) квадратичной иррациональности X = {у/В - U)/V получается по следующим формулам:

Уо = У, Ао = L-J, Uo = U + AoV;

Vn+i = {D- U)/Vn, An+i = [i\/D + Un)/Vn+i], Un+i = А„+1У„+1 -