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

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

Содержание

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

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

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

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

a = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3
\cdots
rn - 1 = rnqn

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

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

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

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

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

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

r1 = a + b( - q0)
r2 = br1q1 = a( − q1) + b(1 + q1q0)
\cdots
(a,b) = rn = as + bt

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

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

\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}].

Примеры реализации

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

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);
}

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 
 КОН НОД;

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home