- 大きな数の掛け算は難しいです。 1971年、2人のドイツ人教授がそれを簡単にするアルゴリズムを予言しましたが、誰もそれを証明することはできませんでした。
小学校からずっと、複雑な掛け算は頭の痛い問題でした。 しかし、オーストラリアのニューサウスウェールズ大学シドニーの助教授が、幼い頃に多くの人が教わる「長い掛け算」よりも効率的な、巨大な数の掛け算の新しい方法を開発しました。
「より技術的には、整数の掛け算の複雑性に関する、1971 年のシェーンハーゲとストラッセンの予想を証明しました」と、デビッド ハーベイ准教授は以下のビデオで述べています。 2007年にさらに高速な方法が開発されたものの、現在ではほとんど使われていない。
シェーンハーゲとストラッセンは、n * log(n) の基本演算を使って n 桁の数字を掛けるアルゴリズムが存在するはずだと予言したと、ハーヴェイは述べています。 彼の論文は、それが存在することを証明する最初の既知のものである。
Harvey は、314 に 159 を掛けたものを例として挙げました。 この問題を解くために、ほとんどの人は個々の数字を掛け合わせ、その合計を足すように教わります。
9に4、1、3をかけ、次に5に4、1、3をかける、というように。 その結果、9桁ずつの積になる。
この方法は、nを何回も掛け合わせなければならないので、n2とかnの2乗と呼ばれています。 これで正しい答えが得られますが、シェーンヘイジとストラッセンはもっと速い方法を考案しました。 n2 を超えてより小さいものに移行することができましたが、n * log(n) という形でまだ課題が残っていました。
数学の問題の途中でこの単語を見ると、代数の授業でやったように目が点になる人もいるかもしれません。 復習として、log は対数の略で、数の2乗や3乗、あるいはそれ以上の指数を読み解くのに役立ちます。 つまり、2⁵は32ですが、対数で表すと、log₂(32)=5となります。 口幅ったいようですが、対数は数字が大きくなると非常に重要です。
Schönhage-Strassen 法は非常に高速だと Harvey は言っています。 もしコンピュータが、2つの数字がそれぞれ10億桁ある問題で、学校で教わった二乗法を使ったら、何ヶ月もかかるでしょう。 シェーンハージ・シュトラッセン法を使ったコンピュータなら、30秒でできる。
しかし、もし数字が何兆、あるいはそれ以上に増え続けるなら、フランスのエコール・ポリテクニックでハーベイと共同研究者のヨリス・ファン・デル・ホーヴェンが開発したアルゴリズムは、1971年のシェーンハージ・シュトラッセン法よりも速く解を見つけることができるかもしれません。
「これは、たとえば割り算や平方根など、あらゆる種類の演算をより効率的に行えるということです。 「円周率の桁も以前より効率的に計算できるようになりました。 さらに、巨大な素数に関する問題にも応用できます」
「人々はほぼ 50 年間、このようなアルゴリズムを探し求めてきました」と彼は続けます。 誰かが最終的に成功することは、当然の結論ではありませんでした。 シェンハーゲとストラッセンが間違っていて、そのようなアルゴリズムは不可能であることが判明したかもしれません。
「しかし、今はもっとよく分かっています」と彼は言います。