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

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

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

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

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

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

a = bq₀ + r₁

b = r₁q₁ + r₂

r₁ = r₂q₂ + r₃

r_{n − 1} = r_nq_n

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

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

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

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

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

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

r₁ = a + b( - q₀)

r₂ = b − r₁q₁ = a( − q₁) + b(1 + q₁q₀)

(a,b) = r_n = as + bt

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

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

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

.

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

.

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

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

[править] Python

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

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

[править] Си

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.