乘法的完美演算法是什麼？數學家可能才剛剛找到答案

自乘法發明以來，數千年已經過去了，但是直到最近，數學家可能才讓這一「技藝」接近完美。你或許會好奇，難道我們至今還沒有完美的乘法計算方法嗎？我們自小從課堂里學的方法難道不夠好嗎？事實上，乘法演算法是數學裡的一個活躍的研究領域。

現有的方法雖然簡單且看似高效，但它卻不適用於極度大的數字，例如那些超過十億位的數字。無論是計算圓周率還是尋找大的質數，其中所涉及的計算問題的複雜性歸根結底都源自於乘法的速度。3月18日，數學家David Harvey和Joris van der Hoeven（分別來自新南威爾士大學和巴黎綜合理工大學）在HAL（法國國家科學研究中心機構庫）提交了一篇論文，論文描述了一個將兩個非常大的數字相乘的新方法，這是迄今為止發現的最快、最高效的乘法演算法。

當我們想知道計算機能多快的解決一些數學問題時，整數間的乘法就是其中最基本的關鍵所在。當要計算的數字非常大時，衡量速度的最重要標準就是隨著數字的位數增加，所需的運算量會增長得多快。

幾乎我們所有人從課堂里學到乘法方法都一樣：我們將兩個要相乘的數上下寫在一起，然後用底下數字的每一位去乘以上面數字的每一位，最後再將結果加起來。也就是說當我們要做一個兩位數乘以兩位數的乘法時，需要總共做四次小的乘法來得到最終的乘積。

○傳統演算法2位數相乘，需要做4次單位數字相乘，再求和才能得到結果。

用這種「進位」方法來做n位數乘以n位數的乘法時，一般需要n2步，所以3位數相乘需要做9次乘法，而100位數相乘則需要做10000次乘法。也就是說這種方法只適用於只有幾位數的數字相乘，但在面對將數百萬位或數十億位的數字時，便會陷入困境。

○傳統演算法的4位數相乘，需要做16次單位數字的乘法，在求和。

可是在精確計算圓周率或者搜尋大型質數中，我們必須進行這樣的運算。如果用這種方法做兩個10億位數的數字相乘，大約將需要花費30年的時間。

1960年，被譽為20世紀最偉大的數學家之一的柯爾莫果洛夫（Andrey Kolmogorov）曾斷言，不存在通用的能讓數字相乘在少於n2步之內完成的運算方法。而當時年僅23歲的數學家Anatoly Karatsuba卻認為——有！經過一周的搜索之後——他找到了。1962年，他正式發表了他的Karatsuba演算法。

Karatsuba的演算法需要將數字分解，並以一種新穎的方式重新組合它們，然後用少量的加法和減法來替換大量的乘法運算。這一方法能節省時間，因為相比於乘法的n2步，加法只需2n步。

○Karatsuba演算法的2位數相乘，只需要3次乘法運算（B、C、E），在加上加減法運算。

當處理較大的數字時，可以重複使用Karatsuba演算法，將原始數字進行拆分。每進行一次拆分，就可以用加法和減法來代替需要很多步驟才能計算的乘法。而對於計算機來說，加法運算比乘法運算要更快。Karatsuba的演算法能將n位數的數字相乘的運算量縮減到n^1.58。

○Karatsuba演算法的4位數相乘，只需要3次Karatsuba乘法運算，每次Karatsuba運算包括三次單位數乘法運算，因此總共只需要進行9次乘法運算。

到了1971年，德國數學家Arnold Schonhage和Volker Strassen發表了一種方法，對於n位數的數字相乘（n較大），可以在n×log(n)×log(log(n))步內完成乘法運算。當兩個n等於10億的數字相乘時，Schonhage和Strassen的演算法比Karatsuba的方法節省了大約165萬億步。

Schonhage和Strassen的演算法不僅成為了計算機用來計算大型數據相乘的方法，並且將信號處理領域中的快速傅里葉變換作為了可用於快速乘法演算法的技術。除此之外，他們還推測出應該存在一種比他們的方法更快的演算法：對於n位數的數字相乘，更快的演算法應該只需要n×log(n)個運算步驟便可以完成；並認為這種演算法可能是乘法運算的極限速度。

Sch?nhage和Strassen的方法一直堅挺了36年，直到2007年才被數學家Martin Fürer擊敗。Fürer發現了當時的最快乘法運算方法，但他放棄了精進他的演算法。他曾在一個採訪中表示，這是一個難度極大的挑戰，他對此毫無信心。正因如此，他對新研究的成功才表示出無比的驚訝與興奮。

不過自Fürer之後，數學家們在過去的十年間相繼發現了更快的乘法演算法，每一種都在一點點地逼近n×log(n)，但都沒能完全達到。直到上個月，Harvey和van der Hoeven抵達了這個極限。

新的方法是基於對前人的工作進行改進而得出的成果。他們用了改進過的快速傅里葉變換步，而且在他們的方法中會多次用到快速傅里葉變換，用加法和減法取代更多的乘法。

Harvey和van der Hoeven的演算法證明了乘法的確可以在n×log(n)步內完成，這在理論上能算得上一大突破。但在實踐中，它並不能表現出明顯的優勢，它的高效主要體現在大得驚人的數字相乘上。van der Hoeven說，我們最多可以期待它比已有的演算法快3倍。

在這項研究中，他們只考慮了多於10214857091104455251940635045059417341952位以上的二進位數字，這些數字用0和1進行編碼。不過他們並沒有真實地進行任何大規模的乘法運算，因為這個數字比宇宙中的原子數量還多得多。這意味著計算機根本無法進行這樣的計算，因為沒有足夠的原子來表示如此巨大的數字，更不用說將它們相乘了。他們所做的是提出了一種技術，使得能從理論上證明這種技術將比其他方法更快，或者說至少對於這麼大的數字會是這樣。

而另一個對這個演算法不那麼有利的因素是，現如今的計算機硬體已與20年前的大為不同。在一些新的晶元構架中，乘法運算與加減法運算的速度差距在不斷縮小，甚至有的還能比加減法運算更快。因此在一些情況下，研究人員可能還需要設法用乘法運算來代替加法運算以提高運算速度。

儘管如此，但這一演算法仍有可能在尋找新的質數或精確圓周率方面發揮作用。在乘法運算這樣一個基本問題上能取得這樣的成就無疑是非常了不起的。而且即便硬體會隨時代變化，但一流的演算法是永恆的。不管未來的計算機是什麼樣子，都不會改變Harvey和van der Hoeven找到了迄今為止最有效的乘法演算法的事實。

編譯：佐佑

參考鏈接：

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

[2] https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/

[3] https://www.sciencenews.org/article/mathematicians-may-have-found-fastest-way-multiply-huge-numbers?tgt=nr

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