performance - a と p が n ビット数であるとすると、mod p のビッグ O 実行時間は?

Question

a%p の計算を含むアルゴリズムの実行時間を見つけようとしています。a と p が n ビット数の場合、このステップにかかる時間は?

Answer 1

O(1)ハードウェア実装を使用する場合、モジュロ演算は onです。(理由は、入力値の限られたセットに対するすべての操作が同じセットに含まれているためですO(1)) そうでない場合、任意の長さの整数のソフトウェア実装は、同じ入力数値の除算と同様の複雑さを持つ必要があります。それが正確に何であるかはわかりません。

編集: 予感はしO(n²)ますが、証明の準備ができていません。

EDIT2:複雑さは問題ではなく実装に依存するため、これに対する完全で正しい答えを提供することは非常に困難です。したがって、異なる実装には異なる複雑さがあり、問題は達成可能なパフォーマンスの下限のみを与えることができます解決アルゴリズムの。

ただし、乗算の複雑さの下限などはまだありません。また、モジュロの下限は実際には乗算の下限に依存するため (コメントに投稿されたリンクを参照してください。私はそれを読みましたが、それは良いことです!)、モジュロ実装の複雑さの下限もありません。そのため、モジュロの達成可能なパフォーマンスを正確に見積もることはできません。

しかし、Big-O 記法について話しているので、適切なモジュロ実装は でO(n²)あり、ほとんどは のより小さなサブセットであると安全に言うことができO(n²)ます。