Lobsters | 📄 原文链接 | 2026-07-20 收录

数学家至今不知道最快的乘法算法是什么

来源：scientificamerican.com — 2026-07-13

📋 概述

这篇文章回顾了一个看似简单却悬而未决的数学问题：乘法的最快算法究竟是什么？几千年来，人们用的都是小学教的逐位相乘算法。直到 1960 年，23 岁的 Karatsuba 发现了分治乘法，打破了人们的认知。此后 Schönhage–Strassen 算法和 Harvey–van der Hoeven 算法不断逼近理论下限，但至今没人知道乘法的真正最优时间复杂度。这个问题的答案影响深远——乘法是加密、AI、音频处理等几乎所有计算任务的基础操作，任何效率提升都有巨大的经济价值。

🔑 核心要点

几千年里人们都以为小学教的逐位乘法（O(n²)）是最优算法，直到 1960 年 23 岁的 Karatsuba 推翻了这一猜想。
Schönhage–Strassen 算法（1971）将大数乘法降至 O(n log n log log n)，统治了近半个世纪。
2019 年 Harvey 和 van der Hoeven 证明了理论上界为 O(n log n)的算法存在，但常数项巨大，实践中并不实用。
乘法效率直接关系到加密、AI 推理、机器人、音频处理等领域的性能——在大规模场景下即使是微小的效率提升也有全球经济影响。
核心悬案：O(n log n) 是否就是理论下界？这个问题至今无人能证明或证伪，成为理论计算机科学最重要的开放问题之一。

💡 金句

For millennia, mathematicians believed this to be the fastest multiplication method, until a 23-year-old made a shocking discovery in 1960, which led to a mystery that remains unsolved to this day.

← 返回 Lobsters 首页