数学者が掛け算の完璧な方法を発見

4000年前、バビロニア人は掛け算を発明しました。先月、数学者たちがそれを完成させました。

3月18日、2人の研究者が、2つの非常に大きな数を掛け合わせる、これまでに発見された中で最も速い方法を発表しました。この論文は、数学における最も基本的な演算の一つを最も効率的に実行する手順を見つけるための長年の研究の集大成です。

「基本的に誰もが学校で習う方法が最善だと考えているが、実際にはそれは活発に研究されている分野だ」と論文の共著者であるフランス国立科学研究センターの数学者、ヨリス・ファン・デル・フーヴェン氏は述べた。

円周率の新しい桁の計算から大きな素数の発見に至るまで、多くの計算問題の複雑さは、結局のところ掛け算の速度に帰着します。ファン・デル・ホーヴェン氏は、この研究結果を、他の多くの種類の問題をどれだけ速く解くことができるかという数学的な速度制限を設定するものだと述べています。

「物理学には、光速のような重要な定数があり、それらによってあらゆる現象を記述することができます」とファン・デル・ホーヴェン氏は述べた。「コンピューターが特定の数学の問題をどれだけ速く解けるかを知りたい場合、整数乗算が、そうした速度を表現できる基本的な構成要素として浮かび上がってきます。」

ほとんどの人が掛け算のやり方を同じように学びます。2つの数字を重ね、下の数字のすべての桁と上の数字のすべての桁を掛け合わせ、最後に足し算をします。2桁の数字同士を掛け合わせる場合は、最終的な積を求めるために4回の小さな掛け算を行うことになります。

小学校で習う「繰り上がり法」では、約n ^{2 回の}手順が必要です。ここで、 nは掛け算する数字の桁数です。つまり、3桁の数字の場合は9回の掛け算、100桁の数字の場合は10,000回の掛け算が必要になります。

繰り上がり法は数桁の数字にはうまく機能しますが、数百万桁や数十億桁の数字を掛け合わせると計算が遅くなります（コンピューターは円周率を正確に計算したり、大きな素数を世界中で探すためにこれを行います）。10億桁の数字を2つ掛け合わせるには、10の18乗（10億の2乗）の計算が必要で^、現代のコンピューターでは約30年かかります。

何千年もの間、掛け算をもっと速くする方法は存在しないと広く信じられていました。そして1960年、当時23歳だったロシアの数学者アナトリー・カラツバは、20世紀の偉大な数学者の一人、アンドレイ・コルモゴロフが主催するセミナーに参加しました。コルモゴロフは、n ²ステップ未満の掛け算を実行する一般的な手順は存在しないと主張しました。カラツバはそれがあると考え、1週間の探求の末、ついにそれを見つけました。

カラツバ法は、数の桁を分解し、斬新な方法でそれらを組み替えることで、多数の乗算を少数の加算と減算で置き換えることを可能にします。この方法により、加算はn 2ステップではなく2 nステップで済むため、計算時間を節約できます。

「足し算は学校で1年早く習います。なぜなら足し算の方がずっと簡単で、数字を右から左に読むのとほぼ同じ速さで線形時間でできるからです」とペンシルベニア州立大学の数学者で、2007年に当時最速の掛け算アルゴリズムを作成したマーティン・フューラー氏は述べた。

大きな数を扱う場合は、カラツバ法を繰り返して、元の数を桁数とほぼ同じ数の部分に分割することができます。そして、分割するたびに、計算に多くのステップを必要とする乗算を、はるかに少ないステップで済む加算と減算に置き換えます。

「掛け算の一部を足し算に変えることができ、コンピューターにとっては足し算の方が速くなるという考えだ」とニューサウスウェールズ大学の数学者で新論文の共著者であるデイビッド・ハーベイ氏は述べた。

カラツバの方法は、 n ^{1.58 回}の一桁の乗算のみで数の乗算を可能にしました。その後、1971 年にアーノルド・シェーンハーゲとフォルカー・シュトラッセンは、 n × log n × log(log n ) 回の乗法ステップで大きな数の乗算が可能な方法を発表しました。ここで、log nはnの対数です。10 億桁の数が 2 つある場合、カラツバの方法では約 165 兆回の追加のステップが必要になります。

コンピュータが巨大な数を掛け算する方法であるシェーンハーゲとシュトラッセンの方法には、他に2つの重要な長期的な影響がありました。まず、信号処理分野の高速フーリエ変換と呼ばれる技術を導入したことです。この技術は、それ以降のあらゆる高速乗算アルゴリズムの基礎となっています。

第二に、同じ論文の中で、ショーンハーゲとシュトラッセンは、彼らが発見したアルゴリズムよりもさらに高速なアルゴリズム、つまりn × log n回の一桁演算のみを必要とする方法が存在するはずであり、そのようなアルゴリズムが可能な限り最速であると推測しました。彼らの推測は、乗算のような基本的な演算には、n × log n × log(log n )よりも洗練された極限があるはずだという直感に基づいていました。

「掛け算は非常に重要な基本演算であり、美的観点から言えば、そのような重要な演算には適切な計算量上限が必要であるという点については、ある種の一般的な合意がありました」とフューラー氏は述べた。「一般的な経験から言うと、基本的な事柄を最終的に数学的に解くことは、常にエレガントな結果をもたらすのです。」

シェーンハーゲとシュトラッセンの不格好なn × log n × log(log n )法は36年間も持ちこたえました。2007年にフューラーがそれを打ち破ると、堰を切ったように高速化が進みました。過去10年間、数学者たちは次々とより高速な乗算アルゴリズムを発見してきましたが、どれもn × log nに少しずつ近づいてはいましたが、完全には到達していませんでした。そして先月、ハーヴェイとファン・デル・フーヴェンがそこに到達しました。

彼らの手法は、先行研究の主要な研究を改良したもので、桁を分割し、高速フーリエ変換の改良版を用い、過去40年間に達成された他の進歩も活用している。「私たちは（高速フーリエ変換を）はるかに大胆に用い、一度ではなく複数回使用し、さらに多くの乗算を加算と減算に置き換えています」とファン・デル・ホーヴェン氏は述べた。

ハーヴェイとファン・デル・フーヴェンのアルゴリズムは、乗算がn × log nステップで実行できることを証明しています。しかし、これより高速な方法が存在しないことを証明しているわけではありません。これが最善のアプローチであると立証するのは、はるかに困難です。2月末、オーフス大学のコンピュータ科学者チームは、別の未証明の仮説も正しいとすれば、これが実際に乗算を最速で行う方法であると主張する論文を発表しました。

新しいアルゴリズムは理論的には重要ですが、実際には既存のアルゴリズムと比べてわずかに優れているだけなので、大きな変化はないでしょう。「期待できるのはせいぜい3倍の速度向上です」とファン・デル・ホーヴェン氏は言います。「劇的な変化にはならないでしょう。」

さらに、コンピュータハードウェアの設計も変化しました。20年前、コンピュータは乗算よりも加算の方がはるかに高速でした。しかし、過去20年間で乗算と加算の速度差は大幅に縮まり、一部のチップアーキテクチャでは乗算が加算よりも高速になることもあります。「一部のハードウェアでは、コンピュータに乗算問題を解かせることで、実際に加算の方が高速化できる可能性があります。これはまさに驚異的です」とハーベイ氏は述べています。

ハードウェアは時代とともに変化しますが、最高クラスのアルゴリズムは永遠です。将来のコンピューターがどのようなものになるかに関わらず、ハーヴェイとファン・デル・フーヴェンのアルゴリズムは、依然として最も効率的な掛け算の方法であり続けるでしょう。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事