Самый знаменитый алгоритм

Квант 1985, №11 с. 44-46 Тег 3RZO

Самый знаментий алгоритм

В предыдуших статьях этого раздела приведили многодисленные примеры алгоритмов и рассказывалось об общих принципах их записи на алгоритмическом языке. Здесь же автор подробно остановился на одном единственном алгоритме — это один из самых древних и наверное самый известный математический алгоритм.

Доктор физико-mатематических наук
С. А. АБРАМОВ

В «Началах» Евклида приведен алгоритм нахождения наиболее делителя (НОД) неотрицательных целых чисел, основанный на следующих свойствах этой величины. Пусть $f$ и $g$ — одновременно не равные нулю целые неотрицательные числа, и пусть $f \geq g$ . Тогда, если $g=0$ , то НОД $(f,g)=f$ , а если $g \neq 0$ , то для чисел $f, g$ и $r$ , где $r$ — остаток от деления $f$ на $g$ , выполено равенство НОД $(f,g)=\text{НОД}(g,r)$ : при любом целом $a$ числа $f$ и $g$ имеют те же общие делители, что и числа $g, f-ag$ , а остаток $r$ есть число вида $f-ag$ .

Применение алгоритма Евклида к числам $f$ и $g$ состоит в выполненении друг за другом серии однозпинных шагов, каждый из которых начинается с проверки, равно ли второе число нулю. Если не равно, то вычисляется остаток от деления первого числа на второе, затем первое число заменяется вторым, а второе — вычисляемым остатком, и произходит переход к следующему шагу. Если же второе число равно нулю, то все вычисления прекращаются, а значением НОД объявляется первое число.

Так при вычислении НОД (39,15) переходит от одной пары чисел к другой в следующей последовательности: (39,15), (15,9), (9,6), (6,3), (3,0). Получаем, что НОД (39,15)=3.

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

Задание 1. Найдите НОД (21042, 18921).
Задание 2. Полностью сократите дробь, записываем которую есть $\underbrace{3\dots3}_{n}$ , а запись значения $-3\dots3, m>n$ .

Большинство древних алгоритмов со временем вытесяло из вычисли-

тельной практики более новых алгоритмов. Алгоритм Евклида избежал этой части прежде всего благодаря своей экономности. Значение НОД(f,g) можно вычислить многоими способами, например с помощью следующого тривиального алгоритма: если $g=0$ , то взять в качестве НОД(f,g) значение $f$ , иначе выбрать из чисел $g,g-1,...,1$ первого, при делении на короче $f$ и $g$ дают нулевые остатки. Но, как и другие подобные алгоритмы, последний алгоритм сликом разорителен. Например, в случае взаимно простых $f$ и $g$ он требует $2g$ делений. Исследуем теперь число делений, требуемых алгоритмом Евклида, и показем, что оно при больших значениях $g$ существует меньше $2g$ . Будем рассматривать последовательность всех остатков, которые вычисляются в процессе выполнения алгоритма Евклида. Полезно обозначить исходные числа не через $f,g$ , а через $f_0,f_1$ (считаем, что $f_0>f_1$ ). Получаемые ненулевые остатки обозначим через $f_2,...,f_n$ , частные от деления $f_0$ на $f_1,f_1$ на $f_2,...,f_{n-1}$ на $f_n$ — через $a_1,a_2,...,a_n$ :

$\begin{align*} f_0 &= a_1f_1 + f_2, \\ f_1 &= a_2f_2 + f_3 \\ \cdots \\ f_{n-2} &= a_{n-1} + f_n, \\ f_{n-1} &= a_nf_n; \end{align*}$

здесь НОД( $f_0,f_1$ )= $f_n$ . Остаток всегда меньше делителя, поэтому $f_0>f_1>f_2>...>f_n>0$ . Вследствие этого каждое из частных $a_1,...,a_n$ больше или равно единице.

Лемма 1. При $i=1,2,...,n-2$ выполняется неравенство $f_i>2f_{i+2}$ .

Доказательство. $f_i = a_{i+1}f_{i+1} + f_{i+2} \geq f_{i+1} + f_{i+2} > 2f_{i+2}$ .

Лемма 2. Пусть $k$ — такое натуральное число, что применение алгоритма Евклида к $f_0,f_1$ не заканчивается после $2k$ делений (то есть $f_{2k+1} \geq 1$ ). Тогда $f_1>2^k$ .

Доказательство. Используя лемму 1, получаем

$f_1 > 2f_3 > 4f_5 > ... > 2^k f_{2k+1} \geq 2^k.$

Теорема. Число делений, требуемых алгоритмом Евклида, не превыходит $2[\log_2 f_1]+2^*$ .

Доказательство. Из леммы 2 вытекает, что если $k$ — натуральное число, для которого $f_1 \leq 2^k$ , то число

$\begin{align*} p - a_{i+1}s) + f_1(q - a_{i+1}t) = f_{i+2}. \end{align*}$

Таким образом, для решения задачи (2) надо применять к $f$ и $g$ алгоритм Евклида, рассматривая на каждом шаге его применения, кроме двух чисел, которые рассматриваются и прежде, еще и соответствующие этим числам множителей $p,q$ и $s,t$ . На первом шаге в качестве множителей, со-

ответствующих исходным числом $f$ и $g$ , берется 1,0 и 0,1. Выполнить деление и получив часть $a$ и некоторый остаток, надо, если остаток не равен 0, перед переходом к следующему шагу вычислить по формулам $p - as$ , $q - at$ множители, соответствующие получению остатку. Последний ненулевой остаток и соответствующие ему множители $u$ и $v$ будут удовлетворять (2).

В процессе применения этого алгоритма к $f = 39$ , $g = 15$ последовательно вычисляются остатки 9; 6; 3; 0 и соответствующие первым тем из них множители 1, -2; -1,3; 2, -5. Таким образом, $39 \cdot 2 + 15 \cdot (-5) = 3 = \text{НОД}(39,15)$ .

Теперь заметим, что алгоритм можно изменить так, что число требуемых им операций сокращится почти в полтора раза: из двух чисел $u$ и $v$ достаточно вычислить вместе с $\text{НОД}(f,g)$ только $v$ , а затем определить $u$ по формуле $u = (\text{НОД}(f,g) - gv)/f$ . Для $f = 39$ , $g = 15$ мы могли бы положить $u = (3 - 15 \times (-5))/39 = 2$ .

Заддача 4. Докажите, что если числа $x$ , $y$ дают некоторое решение уравнения (3), то все решения описываются формулой $x = x + l't$ , $y = y - k't$ , где $k' = k/\text{НОД}(k,l)$ , $l' = l/\text{НОД}(k,l)$ , $t = 0$ , $\pm 1$ , $\pm 2$ .

Заддача 5. Пользовать формулы, выписанных в задаче 4, опишите алгоритм, который позволяет проверить, обладает ли уравнение (3) решения в неотрицательных целых числах и если обладает, то позволяет и построить какое-то одно такое решение.

Последовательные деления с остатком, соответствующие схеме (1), лежат и в основе алгоритма целых дробей, который позволяет получить очень интересные приближения числа $f_1/f_0$ . Цепной дробью (конечной) называется выражение вида

$\frac{1}{b_1 + \frac{1}{b_2} + \dots + \frac{1}{b_k}}$

где $b_1, \dots, b_k$ — натуральные числа. Цепную дробь (5) кратко записывается в виде $[b_1, b_2, \dots, b_k]$ . Так как $f_0 = a_1 f_1 + f_2$ , имеем

$\frac{f_1}{f_0} = \frac{1}{f_0} = \frac{1}{a_1 + f_2}$

Далее этим же способом преобразуем $f_2$ и т. д. В конце концов получим $f_1/f_0 = [a_1, a_2, \dots, a_n]$ . Дополнительно рассмотрим целые дроби $[a_1], [a_1, a_2], \dots, [a_1, \dots, a_{n-1}]$ , значения которых называются nodходящими дробями числа $f_1/f_2$ . Обозначим несократимые формы подходящих дробей через $p_1/q_1, \dots, p_{n-1}/q_{n-1}$ . Следующие свойства приближений числа $f_1/f_0$ подходящими дробями, мы приводим без доказательства:

a) $\frac{f_1}{f_0} - \frac{p_i}{q_i} < \frac{1}{q_i^2}, \quad i = 1, 2, \dots, n - 1$

b) Если для некоторой дроби $u/v$ и подходящей дроби $p_i/q_i$ , $i \leqslant i \leqslant n - 1$ , выполнен

$\left| \frac{f_1}{f_0} - \frac{u}{v} \right| < \left| \frac{f_1}{f_0} - \frac{p_i}{q_i} \right|,$

то $v > q_i$ .

Нетрудно убедиться, что подходящие дроби числа 15/39 (несократимая форма которого есть 5/13) — это 1/2, 1/3, 2/5. Разности между несократным числом и этим дробями соответственно равны -3/26, 2/39, -1/65.

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

Заддача 6. Земной год продолжается 365, 242199 суток. Найдите подходящие дроби числа $\frac{242199}{1000000}$ . Какая именно из этих дробей определяет закон черезования простых и высокоэффективных годов в современном календаре?

Заддача 7. Запишите в виде программы на алгоритмческом языке из вашего учебника (см. также статью A. П. Erшова в предыдущем номере) следующей алгоритмы:

a) тривальный алгоритм для вычисления НОД;

b) алгоритм Евклида для вычисления НОД;

c) алгоритм решения целочисленных уравнений вида $kx + ly = m$ ;

d) алгоритм для представления отношения $f_0/f_1$ в виде цепной дроби.

Алгоритм Евклида допускает и другие обобщения, которые, в частности, используются в приближении irrationalных чисел, в вычислении НОД многочленов. Поэтому и в современной вычислительной практике, основанной на привлечении электронных вычислительных машин, находится применение этого алгоритму, возвращающую к которой 2300 лет.