и если выполнено точно к сдвигов вправо, то отношение X = v/u изменится на X = min(2V(" - «), (" - w)/2M = min(2=JV:/(l - X), (1 - Х)/2Х). Таким образом, неравенство X > х будет справедливо тогда и только тогда, когда 2*А/(1 - А) > а; и (1 - Х)/2Х > X, а это то же самое, что и

< < гЛгГ- (34)

1 + 271 - - 1 + 2*! Поэтому Gn{x) удовлетворяет интересному рекуррентному соотношению

G„.(x) = g2-(G.(j)-G„(j)), (35)

где Оо{х) - 1 - 1 при О < а; < 1. Проведенные вычислительные эксперименты показали, что G„(a;) быстро стремится к предельному распределению Goo(x) = G{x) несмотря на то, что формальное доказательство сходимости представляется неочевидным. Будем полагать, что существует функция распределения G{x). Тогда она удовлетворяет уравнению

ад=1:2-*Кт)-<г;к)) "p-Xsi; (36)

G(0) = 1; G(l) = 0. (37)

Пусть

тогда

G(x) = 5(1/1) - S(x). (39)

Естественно определить

G{l/x) = -G(x), (40)

так что уравнение (39) справедливо для всех а; > 0. Поскольку х изменяется от О до 00, S{x) увеличивается от О до 1. Следовательно, G(x) уменьшается от +1 до -1. Конечно, при а; > 1 функция G(x) перестает быть вероятностью, тем не менее она имеет смысл (см. упр. 23).

Допустим, что имеются степенные ряды а(х), 0(х), jmix), Sm(x), \(х), ц(х),

СГт(х), Тт{х) и р(х), ТакИС, ЧТО

G{x) = a{x)\gx + Р{х) + (тт(ж)COS2тгтlgx +5т(х)sin27гтпIgi), (41)

S{x) - \(x)lgX + IJ,(x) + {am(x) cos27ГТП IgX+ Tm(x) sin 27ГТП Igl) , (42)

p{x) = G(l + x) = pix + ,923; + рзх + pix + ,951 + pex + • • • , (43)

G(x)

1.0 0.8 0.6 0.4 0.2 0.0 -0.2 -0.4 -0.6 -0.8 -1.0

Рис. 10. Предельное распределение отношений в бинарном алгоритме вычисления наибольшего общего делителя.

поскольку можно показать, что этим свойством при п > 1 обладает решение Gn{x) уравнения (35) (см., например, упр. 30). Эти степенные ряды сходятся при ж < 1.

Какие выводы можно сделать относительно а{х), р{х) в уравнени-

ях (36)-(43)? Прежде всего, из уравнений (38), (40) и (43) имеем

25(1) = G(l/(1 + 2х)) + 5(21) = 5(2i) - р{2х). (44)

Соответственно равенство (42) выполняется тогда и только тогда, когда

2\{х) = А(2а;); (45)

2р{х) = р{2х) + А(2а;) - р{2х); (46)

2ат{х) = (Тт{2х), 2тт{х) = тт{2х) при m > 1. (47)

Из (45) следует, что А(а;) есть просто константа, кратная х; так как она отрицательна, можно записать

Л(а;) = -Ai. (48)

(Соответствующий коэффициент приобретает вид

А = 0.3979226811 88316 64407 6707161142 65498 23098+, (49)

но способ, которым его можно вычислить, неизвестен.) Из уравнения (46) следует, что = -А и 2рк = 2*pj. - 2*/>jfe при к > 1; другими словами,

Pk = PklO- - 2-*) при к > 2. (50)

Из уравнения (47) следует также, что оба степенных ряда

<Тт(х) = СГтХ, Гт(х) = ТХ (51)

являются просто линейными функциями. (Но это не распространяется на функции

-(т{х) и 5т{х).)

Если в уравнении (44) заменить х на 1/2а;, то получим

25(1/21) = 5(1/1) + G(x/(1 + I)),

(52)

а последнее уравнение при х, близком к О, при помощи уравнения (39) преобразуется в

2G{2x) + 2S{2x) = G{x) + S{x) + G(a;/(1 + x)). (53)

После подстановки в это уравнение степенных рядов вместо функций коэффициенты при Ig а; в обеих частях должны быть приравнены. Следовательно,

2а{2х) - АХх = а(х) - Хх + а{х/(1 + х)). (54)

Уравнение (54), определяющее а(а;), -рекуррентное. Действительно, предположим, что функция ф{г) удовлетворяет уравнению

(г) = 1(г + ()+(2)), (0) = 0, (0) = 1- (55)

Тогда уравнение (54) означает, что

а{х) = Хф(х). (56)

Более того, из итерационного уравнения (55) следует

, г /1 1 /1 14 1/1 1 1 1 \ \

М = 2(1 + 2(2 + пи + 4T2I + 4T3l) + )

Отсюда получаем, что обобщение ip{z) для степенных рядов имеет вид

ф(г) = E(-1)"-Vnz", ФпЕ () + (58)

п>1 fc=0

см. упр. 27. Эта формула удивительно похожа на выражение б.З-(18), полученное в связи с алгоритмами дискретного поиска в дереве, а в упр. 28 приводится доказательство справедливости формулы ф„ = 0(п~).

Теперь нам известно а{х), за исключением случая, когда А = -pi постоянно. Уравнение (50) связывает функции р{х) и р{х), исключая коэффициент pi. Из ответа к упр. 25 видно, что все коэффициенты функции р(х) могут быть выражены через

Pi, Рз, Р5,---- Более того, константы am и Тт могут быть вычислены при помощи

метода, применяемого для решения задачи в упр. 29; при этом между коэффициентами функций 7т(2;.) и 6т(х) сохраняются сложные связи. Тем не менее, похоже, что единственным способом вычисления всех коэффициентов для различных функций, входящих в выражение для G{x), является итеративное решение рекуррентного уравнения (36) численными методами.

После вычисления хорошего приближения к G(x) можно оценить среднее время выполнения алгоритма В следующим образом. Если и > v и если выполнить к сдвигов вправо, то величина Y = uv будет заменена на Y = (и - v)v/2. Значит, Y/Y равно 2*/(1-А), где А" = v/u равно > а; с вероятностью G(x). Отсюда следует, что число битов в uv уменьшается в среднем на константу

b = E\g(Y/Y) = 2-" (Л(0) + / G(x)fl(x) dx), к>1 -0 /