Алгоритм Евклида

Материал из Википедии — свободной энциклопедии

Алгори́тм Евкли́да — алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм Евклида был известен в древнегреческой математике по крайней мере за век до Евклида под названием «антифайресис» — «последовательное взаимное вычитание». Евклид описал его в VII книге «Начал» для чисел и в X книге «Начал» — для величин.

Содержание

1 Алгоритм Евклида
2 Расширенный алгоритм Евклида и соотношение Безу
3 Связь с цепными дробями
4 Ускоренные версии алгоритма
5 Примеры реализации
6 Ссылки

[править] Алгоритм Евклида

Пусть $a$ и $b$ суть целые числа, не равные одновременно нулю, и последовательность чисел

$a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

определена тем, что каждое $r k$ это остаток от деления пред-предыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, т. е.

a = b q 0 + r 1

b = r 1 q 1 + r 2

r 1 = r 2 q 2 + r 3

$\cdots$

r n - 1 = r n q n

Тогда $(a, b)$ , наибольший общий делитель $a$ и $b$ , равен $r n$ , последнему ненулевому члену этой последовательности.

Существование таких $r 1, r 2,...$ , то есть возможность деления с остатком $m$ на $n$ для любого целого $m$ и целого $n\ne 0$ , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

Пусть $a = b q + r$ , тогда $(a, b) = (b, r).$
$(0, r) = r .$ для любого ненулевого $r .$

[править] Расширенный алгоритм Евклида и соотношение Безу

Формулы для $r i$ могут быть переписаны следующим образом:

r 1 = a + b ( - q 0)

r 2 = b - r 1 q 1 = a ( - q 1) + b (1 + q 1 q 0)

$\cdots$

(a, b) = r n = a s + b t

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве основной теоремы арифметики.

[править] Связь с цепными дробями

Отношение $a / b$ допускает представление в виде цепной дроби:

$\frac ab=[q_0; q_1, q_2,\cdots,q_n]$ .

Отношение $- t / s$ , в расширенном алгоритме Евклида допускает представление в виде цепной дроби:

$-\frac ts=[q_0; q_1, q_2,\cdots,q_{n-1}]$ .

[править] Ускоренные версии алгоритма

Алгоритм может быть записан в общем виде не только для целых чисел, но и для полиномов. Строго говоря, алгоритм работает в любом евклидовом кольце. Одним из методов ускорения целочисленного алгоритма Евклида является выбор симметричного остатка:

$a_i=a_{i-2} \mod a_{i-1},$

причем

$a_i \in \left\{ -\frac{a_{i-1}}{2},\dots,\frac{a_{i-1}}{2} \right\}.$

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

[править] Примеры реализации

Далее приводятся реализации алгоритма Евклида для вычисления НОД на различных языках программирования.

[править] Scheme

Алгоритм вычитанием

(define gcd (lambda (a b)
  (if (> a b) (gcd (- a b) b)
     (if (< a b) (gcd a (- b a))
        a))

[править] Python

Функция в рекурсивном виде:

def gcd(a, b):
  if b == 0: return a
  else: return gcd(b, a % b)

Функция в нерекурсивном виде:

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

[править] Си

int gcd(int a, int b) {
  int c = 0;
  while (b) {
     c = a % b;
     a = b;
     b = c;        
  }
  return abs(a);
}

Та же функция в рекурсивном виде:

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

Алгоритм Вычитанием

 int gcd(int a, int b) {
  while ( a != b) {
     if (a > b) a -= b;
      else b -= a;
  }
 return a;
}

[править] Haskell

gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД от 0 и 0 не определён."
gcd x y = gcd' (abs x) (abs y)
  where gcd' x 0 = x
        gcd' x y = gcd' y (rem x y)

[править] Глагол

 ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; 
 УКАЗ 
   ПОКА (a # 0) И (b # 0) ВЫП 
     ЕСЛИ a >= b ТО 
       a := a ОСТАТОК b 
     ИНАЧЕ 
       b := b ОСТАТОК a 
     КОН 
   КОН; 
   ВОЗВРАТ a + b 
 КОН НОД;

[править] Pascal

 function nod(var a, b:longint):longint; 
 begin
  while (a<>0) and (b<>0) do 
  if a >= b then a := a mod b 
            else b := b mod a;  
  nod:=a+b; 
 end;

В рекурсивном виде:

 function nod(var a, b:longint):longint; 
 begin
  if (a=0) or (b=0) then if a=0 then nod:=b
                                else nod:=a
                    else if a >= b then nod:=nod(a mod b,b) 
                                   else nod:=nod(a,b mod a);   
 end;

[править] Prolog

 ?GCD(a,b,x)
 
 GCD(0,b,b) <- 
 GCD(a,0,a) <-
 GCD(a,b,x) <- a >= b, m is a mod b, GCD(m, b, x)
 GCD(a,b,x) <- a < b, m is b mod a, GCD(a, m, x)

[править] Ссылки

И. М. Виноградов, Основы теории чисел.
Р.Курант, Г.Роббинс, Что такое математика? Дополнение к главе I, § 4.
J. von zur Gathen, J. Gerhard, "Modern Computer Algebra", ISBN 0-521-82646-2

Категории: Теория чисел | Алгоритмы