数学者はまだ、数を掛ける最速の方法を知らない

小学校の生徒は、一桁の数字の九九を覚えるかもしれませんが、先生が三桁の掛け算を求めたときには、丸暗記だけでは通用しません。これにはアルゴリズムが必要です。生徒たちは、一方の数をもう一方の上に積み重ね、下の数字の各桁を上の数字の各桁で掛けるように教えられます。何千年もの間、数学者はこれが最も速い掛け算の方法だと信じていましたが、1960年に23歳の学生が衝撃的な発見をし、それは今日まで未解決の謎につながりました。 この謎は、デジタル世界に関わるすべての人にとって重要です。なぜなら、掛け算はコンピュータの基本的な演算だからです。暗号化、ロボット工学、人工知能、音声処理、そして私たちがシリコンチップに任せるほぼすべてのことは、掛け算、時には巨大な数を何度も掛けることを伴います。この規模では、単純な操作でさえボトルネックとなり、わずかな効率化でも世界経済に影響を与える可能性があります。 そのボトルネックの性質を理解するために、小学校で習うアルゴリズムがどのように規模を処理するかを見てみましょう。二桁の数を二つ掛けるとき、四回の単桁掛け算を行います。これを三桁の数のペアに増やした場合、九回の単桁掛け算を行います。ワークロードは桁数の二乗（n^2、nは掛けられる数の桁数）で増加します。このようなアルゴリズムを分析する際、コンピュータ科学者は速度を秒単位で測定しません。なぜならそれはハードウェアに依存するからです。代わりに、計算ステップ数を数えます。また、掛け算の際の繰り上がりにかかる時間のような、些細な管理上の詳細も無視します。数が十分に大きくなると、それらの低レベルの操作は重要でなくなり、より集中的な操作によって完全に影が薄くなります。コンピュータ科学者は、計算ステップ数を「ビッグオー記法」と呼ばれるもので表します。例えば、小学校で習うアルゴリズムはO(n^2)ステップかかります。これは「オーダーnの二乗」と読みます。大まかに言えば、数が二倍長くなると、アルゴリズムの実行には四倍の計算作業が必要になります。数が千倍長くなると、百万倍（1,000の二乗）の作業が必要になります。 科学ジャーナリズムを支援するために この記事を楽しんでいただけたなら、受賞歴のあるジャーナリズムを購読して支援することを検討してください。購読することで、今日の私たちの世界を形作る発見とアイデアに関する影響力のあるストーリーの未来を確保することに貢献できます。 古代から、数学者はO(n^2)が掛け算の固有の速度限界であると疑ってきました。著名なソ連の数学教授アンドレイ・コルモゴロフは、O(n^2)の速度限界を正式な推測として提示し、1960年のモスクワ国立大学でのセミナーで言及しました。数学者が推測を提示するたびに、彼らは一種の旗を立て、他の誰かがそれを証明または反証するのを待ちます。当時23歳の聴衆の一人であったアナトリー・カラツバは、わずか一週間で戻ってきて、コルモゴロフが間違っていることを証明しました。コルモゴロフは茫然としました。この結果は、権威あるソ連科学アカデミー紀要に掲載されましたが、面白​​いことに、カラツバはそれを書いていませんでした。コルモゴロフ自身が正式な証明を書き、カラツバを筆頭著者にリストアップして出版を提出しました。カラツバが論文のことを知ったのは、郵便で再刷りを受け取ったときでした。 カラツバの天才は、高価で時間のかかる掛け算を、安価で速い足し算と交換できることに気づいたことでした。二つのn桁の数を足すのにかかる時間はO(n)だけです。なぜなら、それは掛け算のように下の数字の各桁に対して上の数字全体をスキャンするのではなく、桁を一度だけスキャンするだけだからです。カラツバが掛け算を足し算と交換した方法を見るために、小さな例を見てみましょう。この方法は、このような単純な問題には複雑すぎますが、数が大きくなると意味のある時間を節約できます。 この簡単な例で、12 × 34 を計算してみましょう。 まず、両方の数を十の位と一の位に分けます。a = 1、b = 2（12の場合）、c = 3、d = 4（34の場合）とします。代数的に、12 × 34 を (10a + b) × (10c + d) と書き直すことができます。 これを展開すると、100(ac) + 10(ad + bc) + (bd) となります。 伝統的な方法で方程式を解くには、四つの別々の掛け算を行う必要があります。ac = 3、ad = 4、bc = 6、bd = 8 です。これは、小学校で習う積み重ね法が要求することと全く同じです。（100や10を掛けることは、数字の末尾にゼロを付けるだけなので、掛け算として数えないことに注意してください。）カラツバは、素晴らしい代数的なトリックに気づきました。最初の項と最後の項、ac と bd を計算したら、厄介な真ん中の項 (ad + bc) を二回ではなく一回の掛け算で求めることができます。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 はすでに計算済みなので、右辺には追加の掛け算が一つと、いくつかの足し算と引き算しか含まれていないからです。 100(ac) + 10(ad + bc) + (bd) に戻ると、四回の掛け算ではなく三回で済みます。ac と bd は直接計算し、その後カラツバのトリックを使って (ad + bc) を一つの掛け算で計算します。ac = 3、bd = 8、(ad + bc) = 10 を代入すると、答えは 408 になります。 私たちは手順から掛け算を一つ減らしました。それがわずかに思えるなら、カラツバにはもう一つ洞察があります。より大きな数を掛ける場合を考えてみましょう：1,234 × 5,678。以前のように半分に分けます。a = 12、b = 34、c = 56、d = 78 とし、問題を (100a + b) × (100c + d) = 10,000(ac) + 100(ad + bc) + (bd) と書きます。 これを三回の掛け算で解くことができます。しかし、それらの掛け算は二桁の数を含みます。幸いなことに、二桁の数をそれぞれ三回の単桁掛け算だけで掛ける方法を知っています！合計で、伝統的な方法では16回の単桁掛け算が必要だった問題が、ここではわずか9回で済みます。カラツバのトリックを大きな数に再帰的に適用することで、節約効果は積み重なります。入力数を半分にし、その半分をさらに半分にし、というように、この四対三の交換をすべての下位レベルで適用します。このアルゴリズムは、実行時間が約 O(n^1.585) になり、O(n^2) よりも劇的に高速になります。参考までに、千桁の数のペアを掛ける場合、小学校の方法では百万回の単桁掛け算が必要ですが、カラツバのアルゴリズムでは57,000回未満で済みます。 23歳の学生の効率性は、日々実行されているソフトウェアに組み込まれています。その追加のオーバーヘッド（足し算、繰り返し分割と再結合の管理など）のため、小学校のアルゴリズムに対する利点は、数が比較的大きくなるまで現れません。例えば、Pythonは、任意のサイズの整数をスムーズに処理することで有名な人気のプログラミング言語です。Pythonの基盤となるソースコードを覗いてみると（ここで「Karatsuba」を検索）、それがハイブリッドアプローチに依存していることがわかります。