algorithm - Schönhage-Strassenアルゴリズムを理解する（巨大な整数の乗算）

Question

Pythonでは、数千桁の長整数をできるだけ効率的に乗算する必要があります。番号はファイルから読み取られます。

私は整数乗算のためにSchönhage-Strassenアルゴリズムを実装しようとしていますが、その背後にある定義と数学、特に高速フーリエ変換を理解することに固執しています。

実用的な例やいくつかの擬似コードのように、このアルゴリズムを理解するための助けをいただければ幸いです。

Answer 1

Knuth のTAOCPの 4.3.3 章で説明されており、これに使用できる FFT 疑似コードが他の章にも含まれています。

Answer 2

車輪を再発明しないでください。GMP にはこのアルゴリズムの優れた高性能実装があり、純粋な Python で記述されたアルゴリズムは少なくとも 100 倍遅くなります。これは単に Python がインタープリター言語であるためです。gmpyを使用して、Python アプリケーションから GMP を呼び出します。また、このような大きな数の乗算を必要とするアプリケーションに取り組んでいることに興味があります。問題を処理するためのより簡単な方法があるかもしれません。

また、他の回答で述べたように、「数千桁の長さ」は、Schönhage-Strassenを正当化するのに十分な長さではありません（少なくとも10000桁、おそらくそれ以上の桁数が必要です）。Toom-3 のような Toom-Cook のいくつかの変種は、通常、この範囲で使用されます。繰り返しますが、これを Python で自分で記述しないでください。GMP の実装は非常に慎重に最適化されています。

Answer 3

Schönhage-Strassen を実際に使用する価値があるとすれば、1000 桁は「小さい」数字です。トゥークックの掛け算 を見たことがあるかもしれません。gmpyは、これらの機能を提供する gmp の Python ラッパーです。