где fk{x) = lg(2V(l - x)). Получаем

h {l-x)\n2)-h {l-x)\n2-

При и = V ожидаемое значение числа \%uv будет приблизительно равно 0.9779 (см. упр. 14), поэтому общее количество циклов "вычитание и сдвиг" алгоритма В будет приблизительно равно исходному значению числа Iguw, умноженному на 1/Ь. Учитывая свойство симметрии, это количество приблизительно равно исходному значению числа IgM, умноженному на 2/Ь. В результате выполненных в 1977 году вычислений Ричард Брент (Richard Brent) получил для этой фундаментальной константы значение

2/Ь = 0.705971246101916391529314135852 8817666677-)-. (60)

В результате более глубокого анализа этих функций Бригитта Балле (Brigitte Vallee) высказала предположение, что постоянные АиЬ могут быть связаны примечательной формулой

i = i. (61)

Ь 7Г

Значения, вычисленные Брентом, вполне согласуются с этим далеко нетривиальным утверждением. Вызывает большой интерес анализ алгоритма В, успешно выполненный Балле на основе строгих "динамических" методов [см. Aigorftlimfca 22 (1998), 660-685].

Вернемся к предположению в (32), состоящему в том, что и w v нечетные и изменяются в интервалах 2"* < и < 2"+ и 2" < г; < 2"+. Эмпирические испытания алгоритма В, проведенные с несколькими миллионами случайных значений на входе и с различными значениями тип, взятыми из интервала 29 < m,n < 37, показывают, что в действительности усредненное поведение алгоритма определяется соотношениями

Ск\т + 0.203П -t-1.9 - 0.4(0.6)"-",

£>« m + 0.41n - 0.5 - 0.7(0.6)"»-", "

при довольно небольшом стандартном отклонении от наблюдаемых средних значений. Коэффициенты j и 1 при т в выражениях (62) могут быть строго проверены (см. упр. 21).

Если же предположить, что и и v - любые целые числа, независимо и равномерно распределенные в интервалах

1 < U < 2, 1 < г; < г, (63)

то можно вычислить средние значения величин С и £> по уже имеющимся данным:

С kQJQN + 0{1), D « 1.4Ш + 0(1). (64)

(См. упр. 22.) Это хорошо согласуется с результатами последующих эмпирических экспериментов, выполненных с несколькими миллионами случайных входных данных для N < 30. Эти эксперименты показали, что в качестве подходящих значений

для заданных распределений входных данных и и v можно взять

С = 0.70N - 0.5, D = 1ЛШ - 2.7. (65)

Теоретический анализ непрерывной модели Брента алгоритма Б предсказывает, что при предположениях (63) величины С и D асимптотически равны 2N/b и 4iV/b, где 2/Ь « 0.70597 - константа в (60). Согласование с результатами экспериментов настолько хорошее, что константа 2/Ь Брента должна в равенстве (65) принимать в качестве значения число 0.70, поэтому в уравнении (62) число 0.203 необходимо заменить числом 0.206.

На этом анализ средних значений С и D завершается. Анализ остальных трех величин, присутствующих в формуле для времени выполнения алгоритма В, выполняется довольно просто (см. упр. 6-8).

Теперь, когда примерно известно поведение алгоритма В в среднем, рассмотрим сценарий "наихудшего случая". Какие значения uhv являются в некотором смысле наиболее трудно обрабатываемыми? Предположим, как и ранее, что

[IguJ = m и [lgt;J = n,

и попытаемся найти ииь, такие, при которых алгоритм будет выполняться наиболее медленно. Принимая во внимание, что операции вычитания выполняются несколько медленнее, чем операции сдвига, сформулированный вопрос можно перефразировать так: при каких значениях входных данных и и v потребуется выполнить наибольшее число вычитаний. Ответ звучит несколько неожиданно: максимальное значение величины С равно точно

max(m,n)-t-1, (66)

хотя поверхностный (наивный) анализ позволил бы предположить, что возможны значительно большие значения С (см. упр. 35). Вывод выражения (66), описывающий наихудший случай, довольно интересен, поэтому он предлагается читателям в качестве занимательной задачи (см. упр. 36 и 37).

УПРАЖНЕНИЯ

1. [М21] Приведите простой способ вывода соотношений (8)-(12) из соотношений (6) и (7).

2. [М22] Пусть известно, что число и делит ЫУ2. ..v„. Докажите, что и делит

gcd(u, ui) gcd(u, i>2) •.. gcd(u, Vn).

3. [M23] Покажите, что число упорядоченных пар положительных чисел {u,v), таких, что 1сш(и, ?;) = п, есть число делителей п.

4. [M2i] Покажите, что для любых положительных чисел и и к найдутся такой делитель и числа и и такой делитель v числа v, что и Lv и uv = lcm(u, v).

* 5. [М26] Разработайте алгоритм для нахождения наибольшего общего делителя двух целых чисел, аналогичный алгоритму В, но базирующийся на представлении Этих чисел в уравновешенной троичной системе счисления. Продемонстрируйте выполнение алгоритма на примере вычисления gcd(40902, 24140).

6. [М22] Пусть и и V - случайные положительные целые числа. Найдите среднее значение и среднеквадратичное отклонение величины А, входящей в формулу для времени выполнения алгоритма В. (Это количество сдвигов вправо чисел и и v во время подготовительной фазы.)

7. [М20] Проанализируйте величину В, входящую в формулу для времени выполнения алгоритма В.

► 8. [М25] Покажите, что в программе В среднее значение величины Е приблизительно равно jCcp, где Сер - среднее значение С.

9. [18] Найдите gcd(31408, 2718), выполнив вычисления вручную с использованием алгоритма В, При помощи алгоритма X найдите также такие целые числа тип, чтобы 31408т -t- 2718п = gcd(31408, 2718),

► 10. [НМ24] Пусть Qn-количество упорядоченных пар целых чисел {u,v), принадлежащих интервалу 1 < и, f < п, таких, что и I.V. Назначение данного упражнения - доказать, что lim„ .oo gn/n = б/тг, и тем самым сформулировать теорему D.

a) Используя принцип включения и исключения (раздел 1.3.3), покажите, что

PI Pl<p2

где суммирование выполняется по всем простым числам р,.

b) Функция Мёбиуса р{п) определяется правилами

р{1) = 1, p{pipi .. .рг) = (-1), если р1,Р2, ..,Рг - различные простые числа, и р(п) = О, если п делится на квадрат простого числа. Покажите, что д„ = Ek>i р{к)[п/к].

c) В качестве следствия из (Ь) докажите, что limn-+oo qn/n = I3t>i р{к)/к-

d) Докажите, что (Z)t>i P(*)A)(Z)m>i = 1- Указание. Если ряды сходятся абсолютно, то ~

( Z Ьг./т) = f а/Л /n

Vt>l / \m>l / п>1 Vd\„

11. [М22] Чему равна вероятность того, что gcd(u, v) < 3? (См. теорему D.) Чему равно среднее значение gcd(u, v)?

12. [М24] (Э. Чезаро (Е. Ceskro).) Пусть и и v - случайные положительные целые числа. Чему равно среднее число их общих (положительных) делителей? [Указание. См. тождество в упр. 10, (d) при Ofc = Ьт = 1.]

13. [НМ23] Пусть и и w - случайные положительные нечетные целые числа. Покажите, что с вероятностью 8/7г они взаимно просты.

► 14. [НМ25] Чему равно ожидаемое значение lngcd(u, ?;), если числа и и v {&) случайные положительные целые числа, (Ь) случайные положительные нечетные целые числа?

15. [Мй/] Чему равны значения чисел vi и по окончании выполнения алгоритма X?

► 16. [М22] Разработайте алгоритм деления и на v по модулю т для положительных целых чисел U, D и m при v, взаимно простом с т. Другими словами, ваш алгоритм должен так вычислить W, принадлежащее интервалу О < w < т, чтобы получить uvw (по модулю т).

► 17. [М20] Пусть даны два целых числа и w v, таких, что вьшолняется uv = \ (по модулю 2"). Объясните, как вычислить такое целое число и, чтобы выполнялось uv = 1 (по модулю 2). [Это приводит к алгоритму вычисления обратных к нечетным числам по модулю степени 2, так как можно начать вычисления с таблицы всех обратных значений для е = 8 или е = 16.]