自1971年以來，兩位數(shù)學(xué)科學(xué)家猜測，超級大整數(shù)相乘極限速度將是N log (N)，且無法被超越。近日，該猜測終于被實現(xiàn)：2個10億位超級大整數(shù)相乘，僅需30秒！

超級大整數(shù)相乘極限速度實現(xiàn)了！

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

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

直到現(xiàn)在，這個假設(shè)終于被證明了！

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

論文地址：

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

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

以前，兩個十億位的整數(shù)相乘，若是采用常規(guī)算法，大約需要幾個月才能算出它們的結(jié)果。但是應(yīng)用該新算法，僅需30秒！

數(shù)學(xué)處處充滿驚喜，大數(shù)乘法速度屢破記錄，或已至極限

兩個整數(shù)相乘很簡單對吧？

小學(xué)的時候我們就學(xué)過如何做整數(shù)的乘法運算，例如：

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

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

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

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

科爾莫戈羅夫認為，如果有更簡便的方法，那肯定已經(jīng)人們發(fā)現(xiàn)了，畢竟人類在“乘法”這件事兒上探索了千年之久。

被打臉，更快的方法誕生

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

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

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

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

大數(shù)字相乘在生活中的應(yīng)用

有人會很好奇，誰會用到這么大的數(shù)字來做乘法呢？事實上，現(xiàn)實生活中由大量的應(yīng)用是需要這么做的，最典型的就是密碼學(xué)。

每次我們在互聯(lián)網(wǎng)上進行加密通信時（例如，訪問銀行網(wǎng)站或執(zhí)行網(wǎng)絡(luò)搜索），我們的設(shè)備都會執(zhí)行的乘法次數(shù)是非常恐怖的，涉及數(shù)百甚至數(shù)千位的數(shù)字。

對于一些更深奧的應(yīng)用程序，數(shù)學(xué)家必須處理更大的數(shù)字，數(shù)百萬、數(shù)十億甚至數(shù)萬億的數(shù)字。對于如此龐大的數(shù)字，即使是卡拉蘇巴的算法也是太慢了。

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

極限速度猜測

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

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

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

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

乘法運算速度極限已經(jīng)實現(xiàn)？

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

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

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

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

另一方面，作者還希望通過進一步的改進，使得該算法可以應(yīng)用于只有數(shù)十億或數(shù)萬億位數(shù)的數(shù)字。如果是這樣，它很可能成為計算數(shù)學(xué)家“軍火庫”中不可或缺的工具。

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

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

畢竟，數(shù)學(xué)處處充滿驚喜。

作者簡介

David Harvey

新南威爾士大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院副教授和ARC未來研究員。研究領(lǐng)域包括計算數(shù)論與算術(shù)幾何，多項式與整數(shù)算術(shù)。

所獲獎項：

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團隊組長。主要研究集中在漸近微積分和復(fù)分析的自動化，以及快速算法。

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