Бинарный алгоритм GCD-алгоритма против алгоритма Евклида на современных компьютерах

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

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

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

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

Ответы

Ответ 1

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

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