ウィキペディアから：
「AnindyaDe、Chandan Saha、Piyush Kurur、Ramprasad Saptharishi [11]は、2008年にモジュラー演算を使用して同様のアルゴリズムを提供し、同じ実行時間を達成しました。ただし、これらの後者のアルゴリズムは、非現実的に大きな入力に対してSchönhage–Strassenよりも高速です。」
私はそのような非現実的に大きな整数のサイズに非常に興味があります。
たぶん誰かが特定の方法で両方のアルゴリズムを実装し、いくつかのベンチマークを行うことができましたか？
ありがとう
Fürer のアルゴリズムとそのモジュラー等価 (DSKS) は非常に深い研究テーマであり、今のところ学術的な関心としてのみ残っています。クロスオーバーポイントがどれほど大きいかは、実際には誰にもわかりません。そして、クロスオーバー ポイントは64 ビット コンピューティングの限界をはるかに超えている可能性が高いため、おそらく問題にはなりません。
以前に Schönhage-Strassen を実装したことがあり、Fürer のアルゴリズムがどのように機能するかを理解しています。だから私は両方ともよく知っています。Schönhage-Strassen と Fürer のアルゴリズムの間のクロスオーバー ポイントが非常に高いため、パラメーターを保持できるコンピューターが観測可能な宇宙のサイズよりも大きくなる可能性が非常に高いと言えます。
これは、対数に満たない複雑さがある場合の問題です。Big-O 定数のわずかな違いを補正するには、指数関数的に大きな入力サイズが必要です。
この場合、Fürer のアルゴリズムは非常に大きな Big-O 定数を持つことが知られています。