轉帖自：《環球科學》

四千年前，古巴比倫人最先發明瞭乘法。而歷史上，數學家也在不斷簡化乘法的步驟，直到上個月，兩位數學家發表了迄今步驟最簡潔的乘法運算方法。

上個月，兩位數學家發表的論文指出，他們發現了至今大數字之間計算速度最快的乘法運算。乘法是數學中最基本的運算方式之一，長期以來，科學家都致力於尋找最高效的乘法運算方式，該研究成果的出現標誌著數學家在此方面的探索到達了一個新的高度。

“大家可能會覺得，自己在學校學到的計算方法就是最佳的那種，但事實上，科學家一直都在繼續優化數學運算方法，”法國國家科學研究中心的數學家Joris van der Hoeven說道，他是論文的共同作者。從計算圓周率新數值到尋找大質數，許多計算問題的複雜性，歸根結底來說就是乘法的速率問題。Hoeven在描述他們的論文成果時，認為乘法運算決定著解決其他問題的速度。

“你可以用許多類似光速的物理常數來描述許多現象，” Hoeven說。 “如果你想知道計算機解決某些數學問題有多快，那麼就需要通過整數乘法來表達這些速度。”

傳統的乘法運算

傳統的乘法運算方法

我們現在都在使用學校教授的同一種方式運算乘法。首先將兩個數字分兩排寫，然後用下面數字從個位開始與上面的每一位數字一一相乘，最後排列好再做加法運算。如果你將兩個兩位數相乘，則會出現四次簡單的乘法運算，然後得到得數。

這種方法需要大約(n^²⁾步完成乘法計算，其中n是乘數的位數。 因此，三位數字需要9次乘法，而100位數字需要10000次乘法。因此該方法只適用於位數少的數字，但對於數百萬或數十億的數字就不那麼方便了。如果要將兩個十億位的數字相乘，則需要進行10¹⁸次乘法計算，即使是現代計算機不停歇地工作都大約需要30年才能完成。

幾千年來，人們普遍認為已經不存在更快的乘法運算方式。1960年，23歲的俄羅斯數學家Anatoly Karatsuba參加了由20世紀偉大的數學家之一柯爾莫果洛夫領導的研討會。會上柯爾莫果洛夫斷言，(n^2)是乘法運算所需最少的步驟，不存在更快的運算方式。但Karatsuba認是有更快地乘法運算方式的，並且經過一週的探索就發現了它。

Karatsuba算法

Karatsuba的方法嘗試對數字的位數進行分解並重新組合，運用這種方式時，可以用少量的加法和減法代替大量的乘法。該方法節省了時間，因為完成加法計算時僅需2n步，而不是(n^²⁾步（n同樣代表數字的位數）。

Karatsuba算法

“如果用加法替代乘法的話，你甚至可以在上學前就使用這種方法，因為它更容易，你可以連續地完成，幾乎像從右到左閱讀數字一樣快，”賓夕法尼亞州立大學數學家MartinFürer說道，他在2007年創造了當時最快的乘法算法。

處理大數字時，你可以重複Karatsuba的過程，將原始數字拆分成與位數一樣多的部分。每次拆分，都可以用加法和減法替換掉乘法，這會節省很多步驟。Karatsuba的方法可以將乘法運算步驟減少至(n^^1.58)次。新加坡南威爾士大學的數學家，新論文作者David Harvey說：“把一些乘法轉變成加法後，計算機會運算得更快。”

大數相乘下兩種方法的比較

乘法步驟不斷更新

1971年，ArnoldSchönhage和Volker Strassen發表了一種能在n×log(n)×log（log n）個步驟以內完成的大數乘法。如果是兩個10億位數字相乘，和這種新方法相比，Karatsuba的方法大約需要多運算165萬億個步驟。

Schönhage和Strassen的大數乘法，對未來的研究提供了兩個長遠的影響。 首先，它引入了信號處理技術中被稱為快速傅立葉變換的方法，該技術一直以來都作為快速乘法算法的基礎。

其次，在當時Schönhage和Strassen推測應該還會有一個更快的算法，一種只需要n×log (n)單位數乘法的方法，並且這種算法可能會是最快的。他們推測，一定存在某種像乘法本身那樣基礎的運算，會比n×log n×log（log n）更簡潔。

“乘法的基礎性與重要性無需多言，從美學的角度來說，如此重要的運算方法終會從複雜走向簡單”Fürer說。“一般經驗來看，數學運算到最後都會變得簡潔。”

就這樣，Schönhage和Strassen提出的 n×log(n)×log（log(n)）方法持續了36年。2007年，Fürer超越了它並打開了新的大門。而在2007年至今的十幾年中，數學家也相繼地發現了更快的乘法算法，且每個算法都接近n×log(n)，但又沒有完全達到它。終於在上個月，Harvey和van der Hoeven做到了。

他們的方法總的來說是對之前工作進行了改進。包括拆分數字，使用快速傅立葉變換的改進版本，並綜合了過去40年各種研究的長處。“我們更頻繁地使用快速傅里葉變換，不再是隻使用一次，並用加法和減法代替更多的乘法，”Hoeven說。

發現最新乘法運算方法研究者之一Hoeven

Harvey和Hoeven的算法證明了乘法可以在n×log n步驟內完成運算，但這並不代表沒有更快的方法了。目前最具挑戰的就是要確立Hoeven的方法是最快的，2月底，奧爾胡斯大學的一個計算機科學家小組發表了一篇論文，認為如果另一個未經證實的猜想是正確的話，那Hoeven的乘法運算最快的方法了。

雖然新算法在理論上取得了突破，但它在實際應用中效果甚微，因為它只比之前的算法稍微快一點。 “我們所希望的是，最好的方法運算能力應該比現在的快三倍，”Hoeven說。

此外，計算機硬件的設計也發生了變化。二十年前，計算機執行加法要比乘法快。但在過去20年中，乘法和加法之間的速度差距已大大縮小，在一些芯片架構中，乘法運算甚至比加法還要快。對於一些硬件，“如果你想完成加法計算，你甚至可以讓它們通過執行乘法來完成，這樣說不定還更快。用乘法的運算速度來實現加法，這看起來有些瘋狂瘋。”Harvery說。

硬件會隨著時間而改變，但最佳的算法方式卻是永恆的。無論計算機會發展到什麼程度，Harvey和Hoeven的算法將仍然是最有效的乘法算法。

閱讀更多 1jiaoyu 的文章

關鍵字: 數學 電腦 新加坡