Каков самый быстрый способ проверить, являются ли два заданных числа взаимно простыми?

Один из способов вычислить их НОД и проверить, если он равен 1.Каков самый быстрый способ проверить, являются ли два заданных числа взаимно простыми?

Есть ли более быстрый способ?

источник

2009-09-27 Lazer

Евклидский алгоритм (вычисления gcd) очень быстрый. Когда два числа рисуются равномерно случайным образом от [1, n], среднее число шагов для вычисления их gcd составляет O(log n). Среднее время вычисления, необходимое для каждого шага, является квадратичным по числу цифр.

Существуют альтернативы, которые выполняют несколько лучше (то есть каждый шаг является субквадратичным по количеству цифр), но они эффективны только для очень больших целых чисел. См., Например, On Schönhage's algorithm and subquadratic integer gcd computation.

источник

2009-09-27 11:54:36 jason

Я хотел бы прокомментировать, что это немного грубо, чтобы измерить сложность арифметических алгоритмов, не принимая во внимание арифметические операции. –

В худшем случае количество шагов равно O (log n), когда два числа являются последовательными записями в последовательности Фибоначчи. –

@Pavel Shved: Я принял во внимание стоимость. ср предложение «Среднее время вычисления, необходимое для каждого шага, квадратично по числу цифр». – jason

Если вы работаете на машине, для которой разделение/остаток значительно дороже, чем сдвиги, рассмотрите binary GCD.

источник

2009-09-27 13:31:48

Спасибо, интересно прочитано –

да, очень хорошая статья. – Lazer

Только что реализовано это в f # и его более чем в 2 раза быстрее, чем традиционный GCD Euclid, не может дать точные числа, так как есть другой код, который меняет мои измерения, однако его> 2x быстрее. Хорошо найти Джейсона. – gatapia

Каков самый быстрый способ проверить, являются ли два заданных числа взаимно простыми?

ответ

Смежные вопросы