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

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел.
*-Нравится статья? Кликни по рекламе! :)

Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Впервые, с нормальным вариантом реализации я встретился на 28 стр. 1 тома "Искусства программирования" Д.Э.Кнута.
Позже я пересекся с ним в видео лекции  http://www.intuit.ru/department/algorithms/introprogalgo/4/
Там он проходил в разделе рекурсии, и было объяснено, что с каждой итерациеё число сокращается более чем в 2-е из-за чего max за logM+logN итераций НОД будет найден.

Алгоритм Евклида (описание с Вики)

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

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

a = bq₀ + r₁

b = r₁q₁ + r₂

r₁ = r₂q₂ + r₃

r_{k − 2} = r_{k − 1}q_{k − 1} + r_k

r_{n − 1} = r_nq_n

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

Есть значит такой вот сайтик http://younglinux.info. Меня отсюда будет интересовать  http://younglinux.info/algorithm/euclidean Здесь, кроме всем известного метода, приведен еще и наиболее не практичная версия алгоритма, назовем его, метод последовательной разницы.

Описание алгоритма нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.
2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 1.

 Конкретная реализация алгоритма:

def gcd(a,b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a        
    print (a) 

А вот нормальная его реализация (аналог из видеолекции с применением рекурсии). Тут применена идея поочередного деления, поэтому назовем его , как не трудно догадаться, :)) метод поочередного деления.

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
 

И должен признаться, что с точки зрения производительности он предпочтительнее. Основные причины - стек рекурсиии (т.е. доп. память на хранение и доп. время на доступ к заранее сохраненным данным), об этом вы так же можете услышать из видео лекции. Там же затронули связь НОД и НОК (наименьшее общее кратное).
Вот что написано в вике на этот счет:

Наименьшее общее кратное (НОК) двух целых чисел m и n — это наименьшее натуральное число, которое делится на m и n. Обозначается НОК(m,n) или [m,n], а в английской литературе lcm(m,n).
НОК для ненулевых чисел m, n всегда существует и связан с НОД следующим соотношением:

 Таким образом поиск НОК выглядит следующим образом

def mcd(n,m):
    return (n/gcd(n,m))*m  

Хочу обратить ваше внимание на то, что  сначалы мы делим на НОД а потом умножаем, таким образом мы защищаем себя от переполнения при произведении 2-х больших цифр.

Интересное: Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, связан с числами Фибоначчи:

Теорема (Ламэ, 1845 г.). Пусть n О N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F _{n +2} , b = F _{n +1} , где F _k - k- ое число Фибоначчи.

Доказательство можно посмотреть, например, здесь: http://virlib.eunnet.net/books/numbers/text/10.html
С помощью этой теоремы можно оценить порядок роста алгоритма Евклида. Пусть a будет меньшим из двух аргументов процедуры. Если процесс завершается за k шагов, тогда должно выполняться a>=Fib(k), т.е. приблизительно равно f^5/sqrt(5) - золотое сечение. Следовательно, число шагов k растет как логарифм a(по основанию f)!


Теперь по-поводу тестирования. Для этого я использую стандартный python profile.
Само собой 1 запуск любого из 3-х вариантов будет производителен, посему я сделал это по 2000 раз, чтобы увидеть разницу.
Результат, полностью подтвердил теорию:

• Самым медленным оказался метод последовательной разницы 2004 function calls in 3.086 seconds
• Сильно быстрее - метод поочередного деления в рекурсивном виде 13743 function calls (2004 primitive calls) in 0.088 seconds
• Ну и победитель забега - метод поочередного деления в не рекурсивном 2004 function calls in 0.014 seconds

* - небольшое пояснение ко 2-му результату. Кто-то может не понять откуда берётся 13743 вызова ф-ии. Ответ кроется как раз в рекурсии, а именно в стеке рекурсии. Т.е. эта циферка говорит, что при вызове 2000 поисков НОД, было выполнено 13739 рекурсивных запусков.

Используемая литература:
1.) http://ru.wikipedia.org/wiki/Алгоритм_Евклида
2.) http://ru.wikibooks.org/wiki/Примеры_реализации_алгоритма_Евклида