Время выполнения программы равно

9А + 2В + бС + 3D + £ + 13

машинных циклов. Здесь А = к, В = 1, если на шаге В2 произошло присвоение t h- и (иначе В = 0), С - число шагов, на которых выполняется вычитание, D - число делений пополам на шаге ВЗ и Е - число, показывающее, сколько раз имеет место неравенство на шаге В5. Из вычислений, выполняемых ниже в этом разделе, следует, что в качестве средних значений этих величин в предположении, что входные величины и я v являются случайными в диапазоне 1 < u,v < 2, можно взять А = i, В = i, С = 0.71Л - 0.5, D = 1.4Ш - 2.7 и £ = 0.35Л - 0.4. Поэтому общее время выполнения программы составляет примерно 8.8N + 5.2 циклов; для программы А при тех же предположениях оно равно приблизительно 11.lA?-1-7.1 циклов. Наихудшее возможное время выполнения 13Л + 8 циклов будет при А = О, В = 1, С = N, D = 2N ~ 2, Е = N - 1, т. е. при условии, что и и v принадлежат одному и тому же диапазону. (Соответствующее время выполнения программы А равно 26.8Л + 19 циклов.)

Таким образом, более высокая скорость выполнения итераций в программе В за счет простоты операций компенсирует большее число итераций, требуемых для выполнения программы. Мы установили, что бинарный алгоритм на компьютере MIX вьшолняется на 20% быстрее, чем алгоритм Евклида. Безусловно, при реализации алгоритма на других компьютерах ситуация может измениться, но во всяком атучае оба алгоритма достаточно эффективны. Тем не менее оказывается, что даже такая освященная веками процедура, как алгоритм Евклида, не может противостоять прогрессу.

История бинарного алгоритма нахождения наибольшего общего делителя поразительна: он был известен еще в Древнем Китае. Так, в разделе 6 главы 1 классического труда СЫи Chang Suan Shu ("Девять разделов арифметики", ок. 1 в. н. э.) приведен следующий метод приведения дроби к простейшему виду.

Если возможно выполнение половинного деления, выполнить его.

В противном случае вьшисать знаменатель и числитель дроби и вычесть меньшее

число из большего.

Повторять эту операцию до тех пор, пока числа не станут равными. Сократить дробь на это общее значение.

Если повторная операция снова приводит к половинному делению вместо того, чтобы повторять операцию вычитания (этот пункт не совсем понятен), метод фактически совпадает с алгоритмом В. [См. Y. Mikami, The Development of Mathematics

in China and Japan (Leipzig, 1913), 11; K. Vogel, Neun Biicher arithmetischer Technik (Braunschweig: Vieweg, 1968), 8.]

B. K. Харрис (V. С. Harris) [Fibonacci Quarterfy 8 (1970), 102-103; см. также V. A. Lebesgue, J. Math. Pures Appl. 12 (1847), 497-520] предложил интересный гибрид метода Евклида и бинарного метода. Если числа и и и нечетны и и > и > О, то всегда можно написать

и = qv±r,

где О < г < и и г четно. Если г О, то присваиваем г <- г/2 до тех пор, пока значение г не станет нечетным. После этого присваиваем и <- v, v <- г и повторяем процесс. В последующих итерациях ? > 3.

Обобщения. Методы, используемые для вычисления gcd(u,t;), можно обобщить так, чтобы решать немного более сложные задачи. Например, предположим, нужно вычислить наибольший общий делитель п целых чисел щ, .., и„.

Один из способов вычисления gcd(ui,U2) • • ,w„), если предположить, что все числа Uj неотрицательны, состоит в обобщении алгоритма Евклида следующим образом: если все числа Uj равны нулю, то наибольший общий делитель принимается равным нулю, иначе при наличии только одного ненулевого числа Uj это число и будет наибольшим общим делителем; в противном случае заменяем Uk на Uk mod Uj для всех к ф j, где Uj - минимальное из ненулевых чисел и, и повторяем процесс.

Алгоритм, набросок которого здесь приведен, является естественным обобщением алгоритма Евклида. Он может быть обоснован аналогичным образом. Но имеется более простой метод, основанный на легко проверяемом тождестве

gcd(ui,U2, •••,"») = gcd(ui,gcd(u2,...,u„)). (14)

Чтобы вычислить gcd(ui, из,..., и„), можно поступить так.

Алгоритм С {Наибольший общий делитель п целых чисел). По заданным целым числам ui, U2, ..., Un, где п > 1, этот алгоритм вычисляет их наибольший общий делитель, используя алгоритм для случая п = 2 как подпрограмму.

С1. Присвоить d Un, к <- п - 1.

С2. Если d 1 и > О, то присвоить d <- gcd(ufc,d) и fc fc - 1 и повторить этот шаг. В противном случае d = gcd(ui,..., u„).

Данный метод сводит вычисление gcd(ui,..., и„) к повторным вычислениям наибольшего общего делителя двух чисел. В нем используется то обстоятельство, что gcd(ui,... ,Uk,l) = I. Оно оказывается полезным, поскольку, как отмечалось выше, в 61 случае из 100, если числа u„ i и и„ рассматривать в качестве случайных, вьшолняется равенство gcd(u„ i,u„) = 1. В большинстве случаев значение d на нескольких первых этапах вычисления быстро уменьшается, в результате чего оставшаяся часть вычислений вьшолняется очень быстро. Здесь алгоритм Евклида имеет преимущество над алгоритмом В ввиду того, что время его выполнения определяется, прежде всего, значением min(u,t;), в то время как время выполнения алгоритма В зависит, главным образом, от значения тах(и,и). Поэтому целесообразно выполнять одну итерацию алгоритма Евклида, заменяя число и на и mod v, если и значительно больше числа v, а затем продолжать вычисления по алгоритму В.

Утверждение, что значение gcd(u„ i,u„) будет равно единице в более чем 60 случаях из 100 для случайных исходных данных, является следствием хорошо известного результата теории чисел.

Теорема D (Г. Люсьен Дирихле (G. Lejeune Dirichlet), Abhandlungen Koniglidi PreuB. Akad. Wiss. (1849), 69-83). Если и и v - случайно выбираемые целые числа, то вероятность того, что gcd(u,t;) = 1, равна б/тг w .60793.

Точная формулировка этой теоремы, в которой четко определяется, что имеется в виду под словами "выбирается случайно", а также ее доказательство приводятся в упр. 10. Здесь же ограничимся эвристическим доказательством, показывающим, почему эта теорема правдоподобна.

Если принять без доказательства существование вполне определенной вероятности р того, что и ± V, то можно определить вероятность того, что вьшолняется равенство gcd(u,t;) = d для любого положительного целого числа d, так как gcd(u,t;) = d тогда и только тогда, когда число и кратно d, число v кратно d и u/d ± v/d. Поэтому вероятность того, что gcd(u,t;) = d, равна 1/d, умноженному на 1/d, умноженному нар, т. е. p/d. Просуммируем теперь эти вероятности по всем возможным значениям d. Должно получиться

l = 2p/d2=p(l+i+i + i + ...).

d>l

Так как сумма 1 + \ + ----= Я равна ж/б согласно формуле 1.2.7-(7), для того,

чтобы выполнялось предыдущее соотношение, необходимо, чтобы р = б/л-.

Алгоритм Евклида можно обобщить еще одним способом, имеющим большое значение. Можно вычислить целые числа и и и, такие, что

ии+vv= gcd{u,v). (15)

Одновременно вычисляется и gcd(u, и). Это обобщение алгоритма Евклида удобно описать, используя векторные обозначения.

Алгоритм X (Обобщенный алгоритм Евклида). Для заданных неотрицательных целых чисел и и v этот алгоритм определяет вектор (ui,U2,U3), такой, что uui + VU2 = U3 = gcd(u,t;). В процессе вычисления используются вспомогательные векторы (г»1,1;2,1з), (1,*2>*з); действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

Uti + Vt2 = *3, иЩ + VU2 = из, UVi + VV2 = V3. (16)

XI. [Начальная установка.] Присвоить (ui,U2,U3) <- (1,0,и), (11,12,1з) (0,1,w). Х2. [из = О?] Если vz = О, то выполнение алгоритма заканчивается. ХЗ. [Разделить и вычесть.] Присвоить q +- [из/из], затем присвоить

(*Ь*2,*з) (Ul,U2,U3) - (Vl,V2,V3)q, (Ui,U2,U3) <- (VI,V2,V3), (Vl,V2,V3) <r- (ti,t2,h).

Возвратиться к шагу X2.