最高效的乘法：兩個非常大的數字相乘迄今最快演算法

傳統乘法運算方法與卡拉蘇巴方法的比較

　　新浪科技訊 北京時間5月5日消息，據國外媒體報道，四千年前，巴比倫人發明了乘法，而最近數學家們又對乘法進行了完善，兩位研究人員描述了迄今為止發現的將兩個非常大的數字相乘的最快方法。這篇論文具有重要的意義，標誌著長期以來尋找最高效乘法步驟的努力達到了新的高度。

　　「基本上，每個人都認為你在學校學習的（相乘）方法是最好的，但實際上這是一個活躍的研究領域，」法國國家科學研究中心的數學家、論文合著者約里斯·范德霍芬說道。該論文發表在法國的國家開放存取文獻資料庫Archive ouverte HAL（https：//hal.archives-ouvertes.fr/hal-02070778/document）上。

　　從計算圓周率的新位數到尋找大質數，許多計算問題的複雜性都可以歸結為乘法運算的速度。按照范德霍芬的描述，他們的研究結果其實是為許多其他類型的問題的求解速度設定了一種數學極限。

　　「在物理學中，有一些重要的常數，比如光速，可以用來描述各種現象，」范德霍芬說，「如果你想知道計算機解決某些數學問題的速度能有多快，那麼就可以將整數乘法視為某種基礎，你可以用它來表示這些速度。」

　　大多數人都用同樣的方法學習乘法。我們把兩個數分兩排寫，用下面數字的每一位乘以上面數字的每一位，最後排列好再做加法。如果是兩個兩位數的數相乘，那你一共要做四個較簡單的乘法來得到最終的乘積。

　　這種小學中所教的方法或稱「進位」法需要n^2個步驟，其中n是每個相乘數字的位數。所以3位數需要9次乘法，而100位數需要10000次乘法。

　　這種進位法適用於只有幾個位數的數字，但是當我們將具有數百萬或數十億位數的數字相乘（比如計算機精確計算圓周率，或者尋找大型質數）時，這種方法就會陷入停滯。兩個10億位數的數字相乘需要運行10^18次（10億的平方）的乘法——這將花費現代計算機大約30年的時間。

　　幾千年來，人們普遍認為沒有更快的相乘方法。1960年，23歲的俄羅斯數學家安納托利·卡拉蘇巴參加了由20世紀最偉大數學家之一的安德烈·科爾莫戈羅夫主持的研討會。柯爾莫戈羅夫在會上斷言，沒有少於n^2個步驟的通用乘法過程。卡拉蘇巴認為並非如此。經過一周的努力，他找到了更快進行乘法運算的新方法。

　　卡拉蘇巴的方法涉及將數字按數位分解，並以一種新穎的方式重新組合它們，允許使用少量的加法和減法替換大量的乘法。該方法可以節省時間，因為加法只需2n步，而不是n^2步。

　　「如果用加法的話，你可以在學校里提早一年就使用這一方法，因為它容易得多。你可以連續地相乘，幾乎就像從右到左閱讀數字一樣快，」賓夕法尼亞州立大學的數學家馬丁·富勒說道。他在2007年建立了當時最快的乘法演算法。

　　當處理大數時，你可以重複卡拉蘇巴的過程，將原始數字分解為幾乎與數位同樣多的部分。每進行一次拆分，就可以用加法和減法來代替乘法，從而減少很多步驟。澳大利亞新南威爾士大學的數學家、這篇新論文的合著者大衛·哈維說：「你可以把一些乘法轉化為加法，重點在於，對電腦來說，做加法的速度會更快。」

　　卡拉蘇巴的方法使得僅使用n^1.58個一位數乘法就可以進行大數的相乘。然後在1971年，德國數學家阿諾德·肖恩哈格和沃克爾·斯特拉森發表了一種方法，可以在n×log n×log（log n）個步驟內完成的大數乘法，其中log n是n的對數。對於兩個10億位數的數字，卡拉蘇巴的方法需要大約額外運算165萬億個步驟。

　　肖恩哈格和斯特拉森的方法主要是關於計算機如何運算大數乘法，對未來的研究產生了兩個重要的長期影響。首先，該方法引入了一種來自信號處理領域的技術，即快速傅里葉變換。該技術一直是所有快速乘法演算法的基礎。

　　其次，在同一篇論文中，肖恩哈格和斯特拉森推測應該有一種更快的演算法，一種只需要n×log n個單位數運算的方法，而且這種演算法可能是最快的。他們的推測基於一種直覺，即像乘法這樣的基本運算必須有一個比n×log n×log（log n）更優雅的極限。

　　「人們普遍認為，乘法運算是一項非常重要的基本運算，以至於從美學的角度來看，這麼重要的運算需要一個很好的複雜度邊界，」富勒說，「從一般經驗來說，基本事物的數學最終總是優雅的。」

　　肖恩哈格和斯特拉森提出的n×log n×log（log n）方法直到36年後才被取代。2007年，富勒提出了新的方法，閘門打開了。在過去的十年里，數學家們相繼發現了更快的乘法演算法，每一種演算法都在一點點逼近n×log n，但都沒有完全達到。最終在上個月，哈維和范德霍芬做到了。

　　他們的方法主要是對前人工作進行了改進，包括拆分數字，使用改進版的快速傅里葉變換，並利用了過去40年取得的其他進展。范德霍芬說：「我們以更加頻繁的方式使用（快速傅里葉變換），而不是只使用一次，並且用加法和減法取代更多的乘法。」

　　哈維和范德霍芬的演算法證明了乘法可以在n×log n步內完成，但這並不能證明沒有更快的方法。要確定這是可能的最佳方法要困難得多。今年二月底，丹麥奧爾胡斯大學的一個計算機科學家小組發表了一篇論文，認為如果另一個未經證實的猜想也是正確的話，那麼哈維和范德霍芬確實提出了最快的乘法運算方法。

　　雖然新演算法在理論上具有重要意義，但在實踐中還不會帶來太大的變化，因為它只比已有的演算法好一點點。「我們所期望的是，這種方法的運算速度能比現在快三倍，」范德霍芬說，「不會太過驚人。」

　　此外，計算機硬體的設計也發生了變化。20年前，計算機的加法運算比乘法運算快得多。經過過去20年的發展，乘法和加法之間的速度差距已經大大縮小，在一些晶元架構中，乘法甚至可以比加法更快。哈維表示，利用一些硬體，「你實際上可以通過讓計算機做乘法來加快做加法的速度，這簡直太瘋狂了。」

　　硬體會隨著時代而改變，但一流的演算法是永恆的。不管未來的計算機是什麼樣子，哈維和范德霍芬的演算法仍然是最高效的乘法演算法。（任天）

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