自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ù)字。但他們的算法并沒有達(dá)到這個(gè)理想的結(jié)果,速度慢了一個(gè)log因子(log N)。
而后的研究者們對(duì)此進(jìn)行了不懈的深入挖掘,但直到2007年,Martin Furer的工作也只是接近N log (N)。
猜測(cè)的后半部分是,N log (N)應(yīng)該就是速度的極限——沒有任何可能的乘法算法能做得比這個(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è)的宇宙中也幾乎沒有足夠的空間把它們寫下來(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)該忘記科爾莫戈羅夫的遭遇?!?/p>
畢竟,數(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ì)算開發(fā)和實(shí)現(xiàn)快速、可靠和數(shù)值穩(wěn)定的算法。
-
算法
+關(guān)注
關(guān)注
23文章
4623瀏覽量
93104 -
傅里葉變換
+關(guān)注
關(guān)注
6文章
442瀏覽量
42651
原文標(biāo)題:極限速度!10億位超級(jí)大整數(shù)相乘僅需30秒,半個(gè)世紀(jì)的猜測(cè)終被證明
文章出處:【微信號(hào):AI_era,微信公眾號(hào):新智元】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論