与えられた2つの数値が互いに素であるかどうかを確認する最速の方法は何ですか？

あるかどうかを確認することで、いくつかのより高速な方法はありますか？

2009-09-27 Lazer

ユークリッドアルゴリズム（計算はgcd）は非常に高速です。 2つの数字が[1, n]からランダムに一様に描画されている場合、gcdを計算する平均ステップ数はO(log n)です。各ステップに必要な平均計算時間は、桁数で2次です。

どちらかといえばより良い（つまり、各ステップは桁数が準十字である）代替方法がありますが、非常に大きな整数に対してのみ有効です。例えば、On Schönhage's algorithm and subquadratic integer gcd computationを参照されたい。

2009-09-27 11:54:36 jason

算術演算のコストを考慮せずに算術アルゴリズムの複雑さを測定するのは少し粗いことをお伝えしたいと思います。 –

フィボナッチシーケンスで2つの数字が連続している場合、最悪のケースのステップ数はO（log n）です。 –

@Pavel Shved：私はコストを考慮に入れました。 cf. 「各ステップに必要な平均計算時間は桁数で二次的です」という文です。 – jason

除算/剰余がシフトよりも大幅に高価なマシンで実行している場合は、binary GCDと考えてください。

2009-09-27 13:31:48

ありがとう、面白い読んで –

ええ、そこに非常に良い記事。 – Lazer

これをf＃で実装し、伝統的なユークリッドのGCDよりも2倍以上高速ですが、正確な数値を与えることはできません。グッドジェイソンを見つける。 – gatapia

答えて