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

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

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

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

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

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

論文地址：

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

簡(jiǎn)單來(lái)說(shuō)，這項(xiàng)研究采用了1,729維快速傅里葉變換(FFT)，使得計(jì)算速度達(dá)到了N log (N)——目前理論上的極限值。

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

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

兩個(gè)整數(shù)相乘很簡(jiǎn)單對(duì)吧？

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

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

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

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

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

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

被打臉，更快的方法誕生

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

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

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

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

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

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

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

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

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

極限速度猜測(cè)

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

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

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

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

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

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

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

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

但是，以目前的形式來(lái)看，新算法實(shí)際上并不實(shí)用，因?yàn)檎撐闹薪o出的證明只適用于非常大的數(shù)字。即使每個(gè)數(shù)字都寫在氫原子上，在可觀測(cè)的宇宙中也幾乎沒(méi)有足夠的空間把它們寫下來(lái)。

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

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

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

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

作者簡(jiǎn)介

David Harvey

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

所獲獎(jiǎng)項(xiàng)：

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

主頁(yè)地址：

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

Joris van der Hoeven

CNRS研究主任、MAX團(tuán)隊(duì)組長(zhǎng)。主要研究集中在漸近微積分和復(fù)分析的自動(dòng)化，以及快速算法。

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