Что наиболее эффективно для GCD?

26

Я знаю, что алгоритм Евклида - лучший алгоритм для получения GCD (большой общий делитель) списка натуральных чисел. Но на практике вы можете кодировать этот алгоритм различными способами. (В моем случае я решил использовать Java, но C / C ++ может быть другим вариантом).

Мне нужно использовать максимально эффективный код в моей программе.

В рекурсивном режиме вы можете написать:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

А в итеративном режиме это выглядит так:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Существует также двоичный алгоритм для GCD, который может быть закодирован просто так:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
jonaprieto
источник
3
Я думаю, что это слишком субъективно и, возможно, даже лучше подходит для StackOverflow. «Наиболее эффективный на практике» зависит от многих (даже непредсказуемых) факторов, таких как базовая архитектура, иерархия памяти, размер и форма ввода и т. Д.
Юхо
5
Это тот же алгоритм, выраженный рекурсивным и итерационным способами. Я думаю, что их разница незначительна, так как алгоритм Евклида сходится довольно быстро. Выберите тот, который соответствует вашим предпочтениям.
pad
6
Возможно, вы захотите попробовать профилирование этих двух. Поскольку рекурсивная версия является хвостовым вызовом, не исключено, что компилятор фактически выдает почти тот же код.
Луи
1
это не правильно. должно быть, пока b! = 0, а затем вернуть a. В противном случае это приводит к ошибкам деления на ноль. также не используйте рекурсию, если у вас действительно большие gcds .... вы получаете кучу состояний стека и функций ... почему бы просто не пойти итеративно?
Крис Стрингфеллоу
4
Обратите внимание, что существуют асимптотически более быстрые алгоритмы GCD. Например, en.wikipedia.org/wiki/Binary_GCD_algorithm
Нил Янг

Ответы:

21

Ваши два алгоритма эквивалентны (по крайней мере для положительных целых чисел то, что происходит с отрицательными целыми числами в императивной версии, зависит от семантики Java, для %которой я не знаю наизусть). В рекурсивной версии пусть и будут аргументом го рекурсивного вызова: aябяя

aя+1знак равнобябя+1знак равноaямоdбя

В императивной версии пусть и будут значениями переменных и в начале й итерации цикла. aя'бя'abя

aя+1'знак равнобя'бя+1'знак равноaя'моdбя'

Заметили сходство? Ваша императивная версия и рекурсивная версия рассчитывают абсолютно одинаковые значения. Кроме того, они оба заканчиваются в одно и то же время, когда (соответственно ), поэтому они выполняют одинаковое количество итераций. Таким образом, с точки зрения алгоритма, нет никакой разницы между ними. Любое различие будет зависеть от реализации, в значительной степени зависящей от компилятора, оборудования, на котором он работает, и, вполне возможно, от операционной системы и от того, какие другие программы работают одновременно.aязнак равно0aя'знак равно0

Рекурсивная версия делает только хвостовые рекурсивные вызовы . Большинство компиляторов для императивных языков не оптимизируют их, поэтому вполне вероятно, что генерируемый ими код будет тратить немного времени и памяти на создание стекового фрейма на каждой итерации. С компилятором, который оптимизирует хвостовые вызовы (компиляторы для функциональных языков почти всегда это делают), сгенерированный машинный код вполне может быть одинаковым для обоих (при условии, что вы гармонизируете эти вызовы abs).

Жиль "ТАК - перестань быть злым"
источник
8

Для небольших чисел достаточно двоичного алгоритма GCD.

GMP, хорошо поддерживаемая и проверенная в реальных условиях библиотека, переключится на специальный алгоритм половины GCD после прохождения специального порога, обобщающего алгоритм Лемера. Лемер использует матричное умножение для улучшения стандартных евклидовых алгоритмов. Согласно документам, асимптотическое время работы как HGCD, так и GCD равно O(M(N)*log(N)), где M(N)время умножения двух чисел N-конечностей.

Полную информацию об их алгоритме можно найти здесь .

qwr
источник
Ссылка действительно не дает полной информации, и даже не определяет, что такое «конечность» ...
einpoklum - восстановить Монику
2

Как я знаю, Java вообще не поддерживает оптимизацию хвостовой рекурсии, но вы можете протестировать свою реализацию Java на это; если он не поддерживает, простой for-loop должен быть быстрее, иначе рекурсия должна быть такой же быстрой. С другой стороны, это битовая оптимизация, выберите код, который вы считаете более простым и более читабельным.

Следует также отметить, что самый быстрый алгоритм GCD - это не алгоритм Евклида, а алгоритм Лемера немного быстрее.

PJTraill
источник
Вы имеете в виду, насколько я знаю ? Вы подразумеваете, что спецификация языка не требует этой оптимизации (было бы удивительно, если бы она это сделала), или что большинство реализаций не реализуют ее?
PJTraill
1

Во-первых, не используйте рекурсивность для замены узкой петли. Это медленно. Не полагайтесь на компилятор, чтобы оптимизировать его. Во-вторых, в вашем коде вы вызываете Math.abs () для каждого рекурсивного вызова, что бесполезно.

В вашем цикле вы можете легко избегать временных переменных и постоянно менять местами a и b.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Обмен с использованием a ^ = b ^ = a ^ = b делает исходный код короче, но для его выполнения требуется много инструкций. Это будет медленнее, чем скучный своп с временной переменной.

Флориан Ф
источник
3
«Избегайте рекурсивности. Это медленно »- представлен как общий совет, это фальшивка. Это зависит от компилятора. Обычно, даже с компиляторами, которые не оптимизируют рекурсию, это не медленно, просто потребляет стек.
Жиль "ТАК - перестать быть злым"
3
Но для такого короткого кода разница существенна. Использование стеков означает запись и чтение из памяти. Это медленно. Код выше работает на 2 регистрах. Рекурсивность также означает выполнение вызовов, что больше, чем условный переход. Рекурсивный вызов намного сложнее для предсказания ветвлений и сложнее встроить.
Флориан Ф
-2

Для небольших чисел % довольно дорогая операция, возможно, более простая рекурсивная

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

быстрее? (Извините, код Mathematica, а не C ++)

Пер Александерссон
источник
Это не выглядит правильно. Для b == 1 он должен вернуть 1. И GCD [2,1000000000] будет медленным.
Флориан Ф
Ах да, я ошибся. Исправлено (думаю) и уточнено.
За Александерссон
Обычно GCD [a, 0] также должен возвращать a. Твои петли навсегда.
Флориан Ф
Я понижаю голос, так как ваш ответ содержит только код. Нам нравится сосредотачиваться на идеях на этом сайте. Например, почему% дорогая операция? На мой взгляд, предположение о куске кода не очень хороший ответ для этого сайта.
Юхо
1
Я думаю, что идея, что по модулю медленнее, чем вычитание, можно считать фольклором. Это справедливо как для маленьких целых чисел (вычитание обычно занимает один цикл, по модулю редко делает), так и для больших целых чисел (вычитание является линейным, я не уверен, что лучшая сложность для модуля, но это определенно хуже). Конечно, вам также необходимо учитывать количество необходимых итераций.
Жиль "ТАК ... перестать быть злым"
-2

Алгоритм Евклида наиболее эффективен для расчета ГКД:

Статический длинный gcd ​​(long a, long b)
{
если (б == 0)
вернуть;
еще
вернуть gcd (,% b);
}

пример:-

Пусть A = 16, B = 10.
GCD (16, 10) = GCD (10, 16% 10) = GCD (10, 6)
GCD (10, 6) = GCD (6, 10% 6) = GCD (6, 4)
GCD (6, 4) = GCD (4, 6% 4) = GCD (4, 2)
GCD (4, 2) = GCD (2, 4% 2) = GCD (2, 0)


Так как B = 0, GCD (2, 0) вернет 2. 
Рохит-Пандей
источник
4
Это не отвечает на вопрос. Аскер представляет две версии Евклида и спрашивает, что быстрее. Похоже, вы этого не заметили и просто объявляете рекурсивную версию единственным алгоритмом Евклида и безо всяких доказательств утверждаете, что он быстрее, чем все остальное.
Дэвид Ричерби