最速の掛け算方法は？未だ不明だが、着実に近づいている

掛け算はコンピューティングの至るところで使われている——暗号、AI、音声処理、あらゆる分野だ。何十年もの間、数学者たちは小学校で習う筆算アルゴリズム（O(n²)）が最速だと考えていた。ところが23歳の学生がその常識を打ち破り、今日まで続く競争の火蓋を切った。

小学校筆算のボトルネック

古典的なアルゴリズムは、一方の数のすべての桁をもう一方の数のすべての桁で掛け合わせる。桁数が2倍になると作業量は4倍になる——O(n²)だ。1000桁の数なら、100万回の1桁同士の掛け算が必要になる。小さな数には許容できるが、大規模になると悪夢だ。

カラツバのトリック：掛け算を足し算に置き換える

1960年、アナトリー・カラツバは、いくつかの掛け算をより安価な足し算で置き換えられることに気づいた。2桁の数なら、4回の掛け算の代わりに3回と数回の足し算で済む。これを再帰的に適用すると、計算量はO(n^1.585)に低下する。Pythonは現在、約630桁以上の数に対してこのアルゴリズムを使っている。

ハーヴェイ–ファン・デル・ホーフェン・アルゴリズム

2019年、デイヴィッド・ハーヴェイとヨリス・ファン・デル・ホーフェンはO(n log n)で動作するアルゴリズムを発表した——これは数値を読み込むのとほぼ同じ速さだ。しかし問題がある：カラツバ法を上回るのは、天文学的に巨大で実際には決して現れない数に対してだけだ。これは銀河アルゴリズム：理論的には美しいが、実用的には無関係だ。

次は何か？

O(n log n)という限界は最適に非常に近いが、それが下限であると証明した者はいない。この問いは未だに未解決であり、新たな洞察がコンピュータの効率的な処理の限界を押し広げ続けている。