数学者はまだ、数を掛ける最速の方法を知らない
Mathematicians still don't know the fastest way to multiply numbers (scientificamerican.com)
要約
数を掛ける計算の最速アルゴリズムは、未だに数学界の未解決問題です。1960年に23歳の学生が、従来の計算方法よりも効率的なアルゴリズムを発見しましたが、それ以降もより高速な方法の発見は続いており、その究極の限界はまだわかっていません。この問題は、コンピュータの暗号化やAIなど、現代のデジタル技術の基盤となる計算効率に深く関わっています。
全文翻訳
数学者はまだ、数を掛ける最速の方法を知らない
小学生は一桁の九九を覚えるかもしれませんが、3桁の掛け算となると、単なる暗記では対応できません。これにはアルゴリズムが必要です。生徒たちは、一方の数をもう一方の数の上に重ね、下の数の一桁ずつを上の数の一桁ずつと掛け合わせる方法を教わります。数千年もの間、数学者はこれが最も速い掛け算の方法だと信じていましたが、1960年に23歳の若者が衝撃的な発見をし、それは今日まで未解決の謎につながりました。
この謎は、デジタル世界に関わるすべての人にとって重要です。なぜなら、掛け算はコンピューターの基本的な演算だからです。暗号化、ロボット工学、人工知能、音声処理、そしてシリコンチップに任せるほとんどすべてのタスクには、掛け算、時には巨大な数を何度も掛け合わせることが含まれます。この規模になると、単純な演算でさえボトルネックとなり、わずかな効率化でも世界経済に影響を与える可能性があります。
そのボトルネックの性質を理解するために、小学校のアルゴリズムがどのように規模に対応するかを見てみましょう。2桁の数を2つ掛ける場合、4回の1桁の掛け算を行います。これを3桁の数のペアにすると、9回の1桁の掛け算を行います。作業量は、桁数の二乗(掛け合わせる数の桁数をnとするとn²)でスケールします。コンピューターサイエンティストは、アルゴリズムの速度を秒単位ではなく、計算ステップ数で測定します。また、掛け算の際の繰り上がりなど、細かい管理上の詳細は無視します。数が十分に大きくなると、それらの低レベルな操作は重要でなくなり、より集中的な操作に完全に隠れてしまいます。コンピューターサイエンティストは、計算ステップ数を「ビッグオー記法」と呼ばれるもので表します。例えば、小学校のアルゴリズムはO(n²)ステップかかります。これは「オーダー n スクエア」と読みます。大まかに言えば、数が2倍長くなると、アルゴリズムの実行に必要な計算作業は4倍になります。数が1000倍長くなると、100万倍(1000の二乗)の作業が必要になります。
科学ジャーナリズムの支援について
この記事を楽しんでいただけましたら、購読して、私たちの受賞歴のあるジャーナリズムを支援することを検討してください。購読することで、今日の私たちの世界を形作る発見とアイデアに関する影響力のあるストーリーの未来を確保することに貢献できます。
古代から、数学者はO(n²)が掛け算の固有の速度限界であると疑っていました。著名なソ連の数学教授アンドレイ・コルモゴロフは、O(n²)の速度限界を正式な推測として提示し、1960年にモスクワ国立大学でのセミナー中に言及しました。数学者が推測を提示するたびに、彼らは一種の旗を立て、他の誰かがそれを証明または反証するのを待ちます。聴衆の中にいた当時23歳の学生アナトリー・カラツバは、わずか1週間でそれを反証しました。コルモゴロフは驚愕しました。この結果は権威ある『ソ連科学アカデミー紀要』に掲載されましたが、面白ことに、カラツバ自身はそれを書いていませんでした。コルモゴロフが自分で正式な証明を書き、カラツバを筆頭著者として出版のために提出したのです。カラツバが論文の存在を知ったのは、印刷されたものを郵便で受け取った時でした。
カラツバの天才は、高価で時間のかかる掛け算を、安価で高速な足し算と交換できることに気づいたことです。2つのn桁の数を足すのにかかる時間はO(n)だけです。なぜなら、それは掛け算のように下の数の各桁に対して上の数を完全にスキャンするのではなく、桁を一度だけスキャンするだけで済むからです。カラツバが掛け算を足し算とどのように交換したかを見るために、小さな例を見てみましょう。この方法は、このような単純な問題には複雑すぎますが、数が大きくなると意味のある時間を節約できます。
この基本的な例で、12 × 34 を計算してみましょう。
まず、両方の数を10の位と1の位に分割します。a = 1、b = 2(12の場合)、c = 3、d = 4(34の場合)とします。代数的に、12 × 34 を (10a + b) × (10c + d) と書き換えることができます。
これを展開すると、100(ac) + 10(ad + bc) + (bd) となります。
伝統的な方法でこの方程式を解くには、4回の独立した掛け算を行う必要があります:ac = 3、ad = 4、bc = 6、bd = 8。これは、小学校の筆算方法が要求することと全く同じです。(100や10を掛けるのは、単に末尾にゼロを追加するだけなので、掛け算として数えません。)カラツバは、素晴らしい代数的なトリックに気づきました。最初の項と最後の項、acとbdを計算したら、厄介な真ん中の項(ad + bc)を、2回ではなく1回の掛け算で求めることができるのです。adとbcを個別に計算する必要はありません。
(ad + bc) = ((a + b) × (c + d)) – ac – bd
具体的な数字で言うと:
((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) – 3 – 8 = 10。
上の式の奇妙さに気づいて一時停止してください。これは、12 × 34 を速く掛けるためには、12の1と2、34の3と4を足す必要があることを示唆しています。これはほとんど自然なことではありません。誰かがそれを理解するのに時間がかかったのも不思議ではありません。しかし、結果として作業量が減ります。なぜなら、すでにacとbdを計算しているので、右辺にはさらに1回の掛け算と、いくつかの足し算と引き算しか含まれていないからです。
100(ac) + 10(ad + bc) + (bd) に戻ると、4回ではなく3回の掛け算で済みます。acとbdは直接計算し、カラツバのトリックを使って(ad + bc)を1回の掛け算で求めます。ac = 3、bd = 8、(ad + bc) = 10 を代入すると、答えは408になります。
これで1回の掛け算を節約できました。それがわずかに思えるなら、カラツバにはもう一つ洞察がありました。もっと大きな数を掛ける場合を考えてみましょう:1,234 × 5,678。以前のように半分に分割します:a = 12、b = 34、c = 56、d = 78。問題を (100a + b) × (100c + d) = 10,000(ac) + 100(ad + bc) + (bd) と書きます。
これは3回の掛け算で解決できます。しかし、それらの掛け算は、2桁の数を含みます。幸いなことに、2桁の数をそれぞれ3回の1桁の掛け算だけで掛ける方法を知っています!合計で、従来のやり方では16回の1桁の掛け算が必要だった問題が、ここではわずか9回で済みます。カラツバのトリックを大きな数に再帰的に適用することで、節約効果は累積します。入力数を半分にし、その半分をさらに半分にし、というように、この「4回を3回に」という取引をすべての下位レベルに適用します。このアルゴリズムは、実行時間が約O(n¹․⁵⁸⁵)となり、O(n²)よりも劇的に高速になります。参考までに、1000桁の数のペアを掛ける場合、小学校の方法では100万回の1桁の掛け算が必要ですが、カラツバのアルゴリズムでは57,000回未満で済みます。
この23歳の若者の効率性は、日々実行されているソフトウェアに組み込まれています。追加のオーバーヘッド(足し算、繰り返し分割・結合の管理など)があるため、小学校のアルゴリズムに対する利点は、数が比較的大きくなるまで現れません。Pythonは、例えば、任意のサイズの整数をスムーズに処理することで有名な人気のプログラミング言語です。Pythonの基盤となるソースコードを覗いてみると(「Karatsuba」をここで検索)、ハイブリッドアプローチに依存していることがわかります。中程度のサイズの入力には小学校の算術を使用しますが、数が約630桁に達すると、スイッチが切り替わり、カラツバのアルゴリズムが採用されます。その桁数は地球の基準では巨大に思えるかもしれませんが、コンピューターははるかに大きな数を扱います。(技術的な補足:ほとんどの最新マシンでは、Pythonは大きな数を基数2³⁰で格納しているため、基数2³⁰で70桁というリンクされたカラツバのカットオフは、10進数で約630桁に相当します。)
カラツバのアルゴリズムは、掛け算の究極の速度限界を見つけるための数十年にわたる競争に火をつけました。その探求は2019年に最高潮に達し、数学者のデビッド・ハーベイとヨリス・ファン・デル・ホーフェンは、それまでのブレークスルーをすべて凌駕する、極めて洗練されたアルゴリズムを発表しました。新しいアルゴリズムはO(n × log n)時間で実行されます。ここでlogはnの対数を表し、非常にゆっくりと成長する関数です。これは驚異的な結果です。関数n × log nは、n自体よりもわずかに大きいだけです。これは、2つの巨大な数の積を計算するのに、それらを足す、あるいは最初の場所でそれらを読み取るのにかかる時間よりもほんの少ししか時間がかからないことを意味します(n桁の数をすべて読み取るにはn回の計算ステップがかかります)。
しかし、この勝利には重要な注意点があります。カラツバのアルゴリズムが小学校のアプローチを上回るのは、数が合理的に大きくなった場合だけであるのと同様に、ハーベイ・ファン・デル・ホーフェンアルゴリズムが優位に立つのは、数が真に銀河系規模になるまでです。コンピューターサイエンスでは、「ギャラクティックアルゴリズム」は、十分に大きな数に対しては印象的な効率を発揮しますが、数が大きすぎるため実際には決して有用にならない方法を指す正式な用語です。
そのアスタリスク付きであっても、それは画期的な成果でした。それは原理上、既知の最速の掛け算方法の記録を確立し、原理上だけでなく実際にもO(n × log n)ステップで実行されるアルゴリズムへの道を開く可能性があります。今日、理論計算機科学者は、O(n × log n)が掛け算の可能な最速速度であると広く推測しており、それを正式に証明することが、このニッチな数学分野の聖杯となっています。しかし、歴史が私たちに思い出させてくれるように、広く受け入れられているコンセンサスは数学的な証明ではありません。掛け算の速度限界に関する推測は、以前にも覆されています。