About: ショーンハーゲ・ストラッセン法

ショーンハーゲ・ストラッセン法は、大きな整数の掛け算を高速に計算できるである。1971年にとフォルカー・シュトラッセンによって発見された。2進法で n 桁の整数同士の掛け算の時間計算量はランダウの記号を用いて である。このアルゴリズムではの1つである 2n+1個の要素を持つ整数環での高速フーリエ変換を用いる。 ショーンハーゲ・ストラッセン法は、発見された1971年から、が発見される2007年まで十分大きな整数の掛け算の最速アルゴリズムであった。しかし、ショーンハーゲ・ストラッセン法よりフューラーのアルゴリズムの性能が上回るのは天文学的に大きな整数同士の掛け算に限るため、フューラーのアルゴリズムはほとんど実用されていない。 実際には、ショーンハーゲ・ストラッセン法がカラツバ法やのような従来の手法より性能が上回り始めるのは、2215 - 2217（10進法で10 000 - 40 000桁）同士の掛け算である。GNU Multi-Precision Libraryはアーキテクチャに依存するが 、64ビット演算において少なくとも1728 - 7808ワード（10進法で33 000 - 150 000桁）の大きさの計算において初めてショーンハーゲ・ストラッセン法を用いる。10進法で74 000桁以上においてショーンハーゲ・ストラッセン法を用いるJavaの実装も存在する。