Двоичный алгоритм НОД против алгоритма Евклида на современных компьютерах

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Эта запись в Википедии имеет очень неудовлетворительный вывод: когда-то алгоритм бинарного НОД был на 60 % эффективнее стандартного алгоритма Евклида, но уже в 1998 году Кнут пришел к выводу, что эффективность его современника увеличилась всего на 15 %. компьютеры.

Что ж, прошло еще 15 лет... как эти два алгоритма сочетаются сегодня с достижениями в области аппаратного обеспечения?

Продолжает ли двоичный GCD превосходить алгоритм Евклида в языках низкого уровня, но отстает ли он из-за своей сложности в языках более высокого уровня, таких как Java? Или разница спорна в современных вычислениях?

Почему меня это волнует, спросите вы? Так уж вышло, что сегодня мне приходится обработать около 100 миллиардов из них :) Вот тост за жизнь в эпоху вычислений (бедный Евклид).


java algorithm math numerical-analysis number-theory
person jkschneider    schedule 19.11.2011    source источник
comment
У вас может быть эталон для их тестирования, просто в одном цикле for (например, размером 1000) создайте список случайных чисел, а затем для всех пар чисел вычислите двоичный код, а в другом цикле вычислите евклид НОД, в чем проблема? ИМО, все еще в современных компьютерах двоичный код должен быть быстрее, особенно с большими числами.   -  person Saeed Amiri    schedule 19.11.2011
comment
Я мог бы, и это было бы достаточно репрезентативным для конкретного языка на конкретном процессоре в конкретной ОС. Это достаточно распространенная числовая операция, поэтому мне было любопытно, какое решение сегодня является предпочтительным в высокопроизводительных приложениях.   -  person jkschneider    schedule 19.11.2011
comment
Если вам нужно сделать 100 миллиардов сегодня, любое время, потраченное на обсуждение наиболее эффективного решения, будет стоить вам больше потерянного времени, чем простое внедрение того или другого.   -  person Nick Johnson    schedule 21.11.2011

Ответы (1)


arrow_upward
6
arrow_downward

Ответ, конечно, "это зависит". Это зависит от железа, компилятора, конкретной реализации, чего я забыл. На машинах с медленным делением двоичный НОД имеет тенденцию превосходить алгоритм Евклида. Я тестировал его пару лет назад на Pentium4 на C, Java и нескольких других языках, в целом в этом тесте двоичный gcd ​​с таблицей поиска из 256 элементов превзошел алгоритм Евклида с коэффициентом от 1,6 до почти 3. Евклидов приблизились, когда вместо немедленного деления сначала было выполнено несколько раундов вычитания. Цифры не помню, но бинарный все равно был значительно быстрее.

Если у машины есть быстрое деление, все может быть по-другому, поскольку алгоритм Евклида требует меньше операций. Если разница в стоимости между делением и вычитанием/сдвигом достаточно мала, двоичный код будет работать медленнее. Какой из них лучше в ваших обстоятельствах, вы должны выяснить, сравнив себя.

person Daniel Fischer    schedule 19.11.2011