「史上最快乘法演算法」太快了，發明者正在想怎麼讓它「慢」下來

長乘法還真是一種漫長的演算法呢。圖片來源：David Harvey

翻譯丨楊莉昕

審校丨戚譯引

來源丨科研圈（ID：keyanquan）

兩個數相乘很簡單，對吧？我們在小學就會學習長乘法，就像題圖這樣。類似的方法可以追溯到幾千年前，至少到古蘇美爾人和古埃及人時代。但這真的是求兩個大數的乘積的最好方法嗎？

在長乘法中，我們必須用第一個數的每一位與第二個數的每一位相乘。如果兩個數均有 N 位，總共就是N2次相乘。在上面的例子中，N 為 3， 我們必須做 32= 9 次乘法運算。

約 1956 年，著名蘇聯數學家 Andrey Kolmogorov 猜測這就是兩數相乘的最佳辦法。換句話說，無論你如何安排，運算的工作量至少是 N2量級。位數翻倍意味著工作量增至四倍。

Kolmogorov 認為，如果簡便方法可能存在的話，一定早就被發現了。畢竟幾千年來人們一直在計算乘積。這是「訴諸無知」邏輯謬論的極好的例子。（訴諸無知：如果一個假設沒有被證明是假/真的，那麼這個假設是真/假的。）

更快的演算法？

沒過幾年，Kolmogorov 的猜想就被證明是大錯特錯。

1960 年，23 歲的俄羅斯數學系學生 Anatoly Karatsuba 發現了一種代數技巧，能夠減少需要相乘的次數。例如，運用 Karatsuba 的方法，將兩個四位數相乘只用做 9 次乘法，而不是 42= 16 次。他的方法在位數翻倍時工作量只增至三倍，與傳統方法相比，在數字更大時展現了巨大的優勢。對於 1000 位的數字，Karatsuba 的方法需要的乘法運算次數只有長乘法的大約 17 分之一。

但究竟為什麼要把這麼大的數字相乘呢？事實上，這樣的乘法有大量相關應用。最明顯並且最具經濟效益的一個應用方向就是密碼學。

現實中的大數字

每次你在網路上使用加密交流時，比如登錄銀行網站或進行網路搜索的時候，你的設備會執行大量乘法，其中涉及上百位甚至上千位的數字。在這個過程中，你的設備很可能就使用了 Karatsuba 的技巧。這都是軟體生態系統的一部分，能讓使我們的網頁儘快載入出來。

在一些保密等級更高的應用中，數學家還必須應對更龐大的數字，位數達到上百萬、十億甚至萬億。對於這樣的數字，甚至連 Karatsuba 的演算法都太慢了。

1971 年，德國數學家 Arnold Sch?nhage 和 Volker Strassen 帶來了一個真正的突破。他們解釋了如何使用當時剛剛發表的快速傅里葉變換（fast Fourier transform，FFT）高效地將巨大數字相乘。現在，他們的方法已被數學家經常應用來處理數十億位的數字。

FFT 是 20 世紀最重要的演算法之一。它在日常生活中最常見的應用就是數字音頻：每當你聽 MP3、音樂流媒體或數字電台時，在台後進行音頻解碼的正是 FFT。

還能再快一點嗎？

在 1971 年的論文中， Sch?nhage 和 Strassen 也提出了一個引人注目的猜想。為了解釋它，我得先講一點學術知識。

們的猜想的前半部分是：有可能通過最多 Nlog (N)（即 N 的自然對數的 N 倍）次量級的基本運算來將 N 位數相乘。他們自己的演算法並未完全實現這個目標，它所需的運算次數是理論最小值的 log (log N)（N 對數的對數）倍。然而，直覺讓他們懷疑漏掉了什麼東西，Nlog (N) 應該是可行的。

自 1971 年起的幾十年來，一些研究者已經對 Sch?nhage 和 Strassen 的演算法進行了改進。尤其是 Martin Fürer，他在 2007 年設計的一種演算法已經極其接近難以達到的 Nlog (N) 量級。

他們猜想的第二部分，也是更為困難的部分是：Nlog (N) 應該是基本的運算速度極限。也就是說，不可能有乘法演算法能實現比這更少的運算次數。

我們達到極限了嗎？

幾周前，Joris van der Hoeven 和我發表了一篇研究論文（論文鏈接），描述了一種新的乘法演算法，終於觸及了 N log (N) 這個「聖杯」，解決了 Sch?nhage–Strassen 猜想中「簡單」的部分。

這篇文章還未經過同行評審，所以需要謹慎看待。在數學界，研究成果常常在經歷同行評審之前就被傳播開來。

我們的演算法沒有採用一維 FFT 方法（自 1971 年起關於這一問題的所有研究工作都依靠這種方法），而是使用了多維 FFT 方法。這方法本身並不新，廣泛使用的 JPEG 圖片格式就依靠二維 FFT 方法，三維FFT方法在物理和工程中也有很多應用。

在我們的論文中，我們使用了 1729 維的 FFT 方法。這很難想像，但在數學上並不比二維情況麻煩。

這項新演算法目前還很難得到實際運用，因為我們文章中的證明只適用於大得出奇的數字。即使把每一位數字都寫在一個氫原子上，可觀測的宇宙中也幾乎沒有足夠的空間寫下它們。

另一方面，我們希望通過進一步的改進，能讓演算法適用於只有數十億或萬億位的數字。如果能實現這個目標，它將很可能成為計算數學家的工具包中必不可少的裝備。

如果 Sch?nhage–Strassen 猜想完全正確，那麼理論上，這項新演算法已到了路的盡頭，不可能做得更好了。

就我個人而言，如果猜想最終是錯誤的，那麼我也會非常驚訝。但我們不應忘記發生在 Kolmogorov 身上的事情。數學有時會給人帶來驚喜。

該文作者為新演算法發明人之一David Harvey

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！