2026/07/14 2:21
数学者たちはいまだに数字を最も速く掛ける方法を知っているわけではありません。
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
乗法アルゴリズムの進化は、何世紀にもわたる伝統的な手法から、現代コンピューティングにとって不可欠な革命的速度の向上への変遷を示しています。従来の「筆算（積み上げ）方式」は単純ではあるものの、入力サイズに二乗比例する O(n²) の二次的計算量に苦慮しており、この点は 1960 年にアナトリー・カラツバによって根本的に挑戦されました。彼は高コストな乗法を安価な加算に置き換え、計算量をおよそ O(n^1.585) に削減しました。桁数が 1,000 の数値の場合、筆算方式では 100 万回の単位数の乗法が必要ですが、この方式ではそれを 57,000 回以下に抑えることができます。現在、Python などの実用的なツールでは、630 桁を超える非常に大きな入力のみに対して、この高速な再帰的手法へ切り替えるハイブリッド戦略を採用しています。
最近、デイヴィッド・ハーベイとヨリス・ファンデルホーベンによる画期的な進展により、O(n × log n) の計算量を持つ理論的に最適であるアルゴリズムが提案されました。これは、実際に利益をもたらすのは天文学的大きな数の処理になるため、「銀河系アルゴリズム」とも呼ばれています。乗法は暗号化、AI、ロボティクス、音声処理などのデジタル操作の基盤であり、効率性の向上は世界的に重要です。コンピュータサイエンティストらはこの対数境界が究極的な上限であると推測していますが、これを形式的に証明することは「聖杯」と呼ばれる主要な数学的目標として残っています。これらの限界を達成すれば、大規模な整数算術に大きく依存する重要な分野での性能を大幅に向上させることができます。
Text to translate:
The evolution of multiplication algorithms marks a shift from centuries-old methods to revolutionary speedups essential for modern computing. While the traditional grade-school stacking method, though simple, suffers from quadratic complexity O(n²) where processing time grows with the square of input size, this was fundamentally challenged in 1960 by Anatoly Karatsuba. He replaced expensive multiplications with cheaper additions, reducing complexity to roughly O(n^1.585). For thousand-digit numbers, this requires fewer than 57,000 single-digit multiplications compared to one million for the grade-school method. Today, practical tools like Python use a hybrid strategy, switching to this faster recursive technique only for very large inputs exceeding 630 digits.
Recent breakthroughs by David Harvey and Joris van der Hoeven have proposed a theoretically optimal algorithm with complexity O(n × log n), often called a "galactic algorithm" because its practical benefits will likely only emerge when processing numbers of truly astronomical magnitude. Multiplication is foundational for digital operations like encryption, AI, robotics, and audio processing, making efficiency improvements globally significant. While computer scientists suspect this logarithmic limit is the ultimate ceiling, formally proving it remains a major mathematical goal known as the "holy grail." Achieving these limits would significantly boost performance in critical fields that rely heavily on massive integer arithmetic.
本文
千年続いた「最も速い」乗算法を破壊した若き天才の発見
小学生は九九を暗記していても、三位数の乗算問題には通用しません。そこで習得されるのは、各桁同士を掛け合わせるという単純なアルゴリズムです。何千年間も数学者たちはこれを「最速手法」と信じてきましたが、1960 年に23 歳の若き研究者がその常識を覆す驚くべき発見を行いました。
なぜこの発見が重要なのか
デジタル社会に生きる私たちは誰もが影響を受けています。乗算はコンピュータの基礎演算であり、暗号化、ロボティクス、AI、音声処理など現代技術の根幹を支えています。
- 巨大な計算量: 膨大な数を多数回処理する際、単純な操作がボトルネックとなります。
- 経済的帰結: わずかな効率向上でも、世界的な規模での経済的インパクトをもたらします。
ボトルネックの正体：なぜ掛け算は遅いのか？
学校で習うアルゴリズムが数の増大をどう処理するかを見てみましょう。
- 二桁の数同士の掛け算: 単一桁同士を $4$ 回掛けます。
- 三桁の数同士の掛け算: 単一桁同士を $9$ 回掛けます。
このように、負荷量は数の桁数（$n$）の二乗に比例します（$O(n^2)$）。コンピュータサイエンティストは「秒数」ではなく、計算ステップ数を基準とします。
- 数が $2$ 倍になれば、必要な計算量は $4$ 倍になります。
- 数が $1,000$ 倍になれば、必要な計算量は $100$ 万倍（$1,000^2$）になります。
この $O(n^2)$ が、長らく乗算の速度限界と考えられてきました。
画期的な発見：カラツバのアルゴリズム
ソ連の数学科教授・アンドレイ・コロモゴロフは、「$O(n^2)$ は限界である」という仮説を提示しました。しかし、当時の聴衆にいた23 歳の若き研究者・アナトリー・カラツバは、わずか一週間後にこの仮説の間違いを証明しました。
カラツバの天才的洞察
高価で時間のかかる「掛け算」を、安価で高速な「加算」と交換することで解決します。
- 伝統的な方法: 下の数の各桁に対して上の数全体を一巡する必要があります（合計 $4$ 回の掛け算）。
- カラツバのトリック: 厄介な中間項 $(ad + bc)$ を、2 つの掛け算ではなく1 つの追加の掛け算ステップで求める方法を見つけ出しました。
$$ (ad + bc) = ((a + b) \times (c + d)) - ac - bd $$
具体的な計算例（$12 \times 34$）:
- 分割：$a=1, b=2, c=3, d=4$
- 掛け算の削減:
- $ac = 3$, $bd = 8$ を通常計算。
- $(ad+bc)$ は、
の式で1 回の掛け算のみで解決。((a+b)×(c+d)) - ac - bd
- 結果: 必要な掛け算が $4$ 回から $3$ 回に減ります。
相乗効果：再帰的適用
このトリックをさらに大きな数（例：$1,234 \times 5,678$）に適用し、半分ずつ分割して再帰的に繰り返します。
- 従来の方法: 単一桁の掛け算が $16$ 回必要だった。
- カラツバの方法: 単一桁の掛け算が $9$ 回で済む。
大きな数ほどこの節約効果が相乗的に働きます。最終的な実行時間は $O(n^2)$ から劇的に改善され、概ね $O(n^{1.585})$ となります。
- 千桁の数の計算:
- 学校的方法：単一桁掛け算 $100$ 万回必要。
- カラツバ法：約 $57,000$ 回未満で済み、劇的な高速化を実現します。
実世界での応用：Python の例
この発見は現在の日々のソフトウェアに組み込まれています。ただし、単純な「足し算」や「分割・再結合」のオーバーヘッドがあるため、数が比較的大きい場合のみ有利になります。
例えば人気プログラミング言語Pythonでは、ハイブリッド手法が採用されています：
- 中程度のサイズ: 学校で習う通常の算術を使用。
- 約 $630$ 桁（十進法）に達すると: カラツバのアルゴリズムへ自動切り替え。
※最新のマシンでは、Python は大きな数を $2^{30}$ で格納しており、これは約 $630$ の十進法桁に相当します。
次のフロンティア：理論の限界へ
カラツバの発見は数十年もの競争を火付け、2019 年に頂点に達しました。数学者・デイヴィッド・ハービーとヨリス・ヴァン・デル・ホーフェンにより、さらに高度なアルゴリズムが開発され、世界記録を更新しました。
新しい速度限界：$O(n \times \log n)$
- 性能: 従来の $O(n^2)$ や $O(n^{1.585})$ を凌駕する $O(n \times \log n)$ のスピードを実現。
- 意味: $\log n$ は非常に緩やかに増加するため、この速度は「数を足す」あるいは「数の桁を読み取る」時間とほぼ同等の効率です。理論的な最速到達点に極めて近づいたと言えます。
ただし、注意点もあります：
- 銀河アルゴリズム: 数の大きさがあまりにも巨大すぎて実用性がないアルゴリズムを指す用語です。ハービー・ヴァン・デル・ホーフェンの手法も、非常に大きな数まで有効になります。
まとめ
23 歳の若手研究者が立てた小さな仮説の反証が、現代のデジタル社会を形作っています。この発見は単なる数学的な興味を超え、世界経済に多大な影響を与える可能性を秘めています。現在、理論的な最速である $O(n \times \log n)$ が実際に実装されたアルゴリズムとして、さらに多くの計算処理を可能にしつつあります。