極限速度！10億位超級大整數相乘僅需30秒，半個世紀的猜測終被證明

新智元原創

來源：theconversation

編輯：金磊、小芹

【新智元導讀】自1971年以來，兩位數學科學家猜測，超級大整數相乘極限速度將是N log (N)，且無法被超越。近日，該猜測終於被實現：2個10億位超級大整數相乘，僅需30秒！

超級大整數相乘極限速度實現了！

整數相乘是每個人必學的一個運算，我們通常採用的思路是：第一個數字的n位乘以第二個數字的n位，這就意味著要進行n2次的乘法運算。但當這兩個整數大到一定程度時，這個過程的計算量是相當龐大且驚人的。

當然，前人們已經找到了一些解決方法來改善這一問題。早在1971年，兩位德國數學家就猜測，兩個大數相乘的可以達到一種令人難以置信的速度，即N log (N)。然而，這個聰明的想法幾十年來一直只是假設。

直到現在，這個假設終於被證明了！

澳大利亞新南威爾士大學(UNSW)的數學家、副教授David Harvey近日聲稱，他和他的合著者首次破解了這個由Arnold Sch?nhage 和 Volker Strassen提出，存在近半個世紀之久的數學難題。

論文地址：

https://hal.archives-ouvertes.fr/hal-02070778/document

簡單來說，這項研究採用了1,729維快速傅里葉變換(FFT)，使得計算速度達到了N log (N)——目前理論上的極限值。

以前，兩個十億位的整數相乘，若是採用常規演算法，大約需要幾個月才能算出它們的結果。但是應用該新演算法，僅需30秒！

數學處處充滿驚喜，大數乘法速度屢破記錄，或已至極限

兩個整數相乘很簡單對吧？

小學的時候我們就學過如何做整數的乘法運算，例如：

但是，若是整數長度大到了一定程度，這種方法真的是最好的嗎？

在一般的乘法運算過程中，我們需要把第一個整數的每一位和第二個整數的每一位做乘法。如果這兩個數都有N位，那就是N2(或N x N)相乘。在上面的例子中，N是3，所以我們要做32= 9次乘法。

1956年前後，著名的蘇聯數學家安德烈·科爾莫戈羅夫(Andrey Kolmogorov)推測，這就是兩個整數相乘的最好方法。

換句話說，不管你怎麼安排計算，你要做的功至少與N2成正比。兩倍的數字意味著四倍的工作量。

科爾莫戈羅夫認為，如果有更簡便的方法，那肯定已經人們發現了，畢竟人類在「乘法」這件事兒上探索了千年之久。

被打臉，更快的方法誕生

然而，就在幾年後，科爾莫戈羅夫就被打臉了。

1960年，23歲的俄羅斯數學系學生阿納托利·卡拉蘇巴(Anatoly Karatsuba)發現了一種代數技巧，可以減少所需的乘法次數。

例如，要乘四位數的數，不需要42= 16的乘法，卡拉蘇巴的方法只需要9次。當使用他的方法時，兩倍的數字只意味著三倍的工作量。

而且隨著數字位數的增大，這種方法的有效性越發顯著，對於一千位數字的相乘，比之前的方法所需的乘法次數要少17倍。

大數字相乘在生活中的應用

有人會很好奇，誰會用到這麼大的數字來做乘法呢？事實上，現實生活中由大量的應用是需要這麼做的，最典型的就是密碼學。

每次我們在互聯網上進行加密通信時（例如，訪問銀行網站或執行網路搜索），我們的設備都會執行的乘法次數是非常恐怖的，涉及數百甚至數千位的數字。

對於一些更深奧的應用程序，數學家必須處理更大的數字，數百萬、數十億甚至數萬億的數字。對於如此龐大的數字，即使是卡拉蘇巴的演算法也是太慢了。

1971年，德國數學家阿諾德·紹哈格(Arnold Schonhage)和沃爾克·斯特拉森(Volker Strassen)的工作取得了真正的突破。他們解釋了如何使用快速傅里葉變換(FFT)來有效地對「大數字」做乘法。今天的數學家經常使用他們的方法來處理數十億位數的數字。

極限速度猜測

在他們1971年發表的論文中，他們也提到了一個驚人的猜測。

他們猜測的前半部分是，應該有可能使用最多與N log (N) (N乘以N的自然對數)成比例的一些基本運算來乘N位數字。但他們的演算法並沒有達到這個理想的結果，速度慢了一個log因子(log N)。

而後的研究者們對此進行了不懈的深入挖掘，但直到2007年，Martin Furer的工作也只是接近N log (N)。

猜測的後半部分是，N log (N)應該就是速度的極限——沒有任何可能的乘法演算法能做得比這個更好。

乘法運算速度極限已經實現？

就在前幾周，Joris van der Hoeven和David Harvey共同發表的一篇論文《Integer multiplication in time O(n log n)》描述了一種新的乘法演算法，最終達到了N log(N)這一「聖杯」。

該演算法突破性重點在於使用多維FFT，而不是僅僅使用一維FFT。自1971年以來，在很多領域都會涉及多維FFT的應用，例如JPEG格式圖像依賴於二維FFT，而三維FFT在物理和工程中有很多應用。

而在這篇論文中，所用到的FFT維度高達1,729。

但是，以目前的形式來看，新演算法實際上並不實用，因為論文中給出的證明只適用於非常大的數字。即使每個數字都寫在氫原子上，在可觀測的宇宙中也幾乎沒有足夠的空間把它們寫下來。

另一方面，作者還希望通過進一步的改進，使得該演算法可以應用於只有數十億或數萬億位數的數字。如果是這樣，它很可能成為計算數學家「軍火庫」中不可或缺的工具。

若Schonhage-Strassen猜想是正確的，那麼從理論的角度來看，新演算法就是這條路的終點——不可能做得更好。

但論文作者也表示：「若猜想被證明是錯誤的，我會感到非常驚訝。但我們不應該忘記科爾莫戈羅夫的遭遇。」

畢竟，數學處處充滿驚喜。

作者簡介

David Harvey

新南威爾士大學數學與統計學院副教授和ARC未來研究員。研究領域包括計算數論與算術幾何，多項式與整數算術。

所獲獎項：

2017–2021: Counting points on algebraic surfaces ($805,054)ARC Future Fellowship, FT160100219

2015–2017: Fast algorithms for zeta functions of algebraic varieties ($325,500)ARC Discovery Project, DP150101689

2012–2014: Counting solutions to equations over fields of large characteristic ($375,000)ARC Discovery Early Career Researcher Award, DE120101293

主頁地址：

https://web.maths.unsw.edu.au/~davidharvey/

Joris van der Hoeven

CNRS研究主任、MAX團隊組長。主要研究集中在漸近微積分和複分析的自動化，以及快速演算法。

曾與Matthias Aschenbrenner合作共同出版了《漸近微分代數與變級數模型理論》一書，證明了漸近微分代數的量詞消去定理。另一個主要研究課題是具有特殊函數或更一般的微分方程解的複分析和計算的自動化。一方面，這導致了一些有趣的理論問題，如可計算性、零點測試、奇點等。另一方面，需要為多精度計算開發和實現快速、可靠和數值穩定的演算法。

主頁地址：

http://www.texmacs.org/joris/main/joris.html

參考鏈接：

https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923

https://hal.archives-ouvertes.fr/hal-02070778/document

https://www.iflscience.com/editors-blog/newly-cracked-math-puzzle-allows-faster-multificaiton-of-large-numbers/

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