早在數千年之前，巴比倫人就已經發明了乘法。而就在上個月，數學家們又對這一運算方式進行了優化，使它越來越完美。
最近，兩位研究人員有可能發現有史以來最快的計算兩個超大數的乘法運算方式。這篇論文的誕生，也意味著數學界最基本的運算方式又有了更新更有效的運算過程，有望破解了一個已經存在近半個世紀的數學問題。
法國國家科學研究中心數學家，這篇論文的共同作者之一 Joris van der Hoeven 說道，「大部分人都以為自己在學校裡面學到的方法就是最好的方法，但是實際上在研究界，有關乘法的計算方法領域一直是十分活躍的，而且不斷有著新的突破和優化。」
圖丨 有史以來最快大數相乘算法的兩位發明人，上為法國國家科學研究中心的數學家 Joris van der Hoeven ，下為新南威爾斯大學教授 David Harvey。在計算超大數時，下圖中的傳統計算方法會變得十分吃力（來源：École Polytechnique）
許多數學計算領域的難題，從圓周率的計算到尋找最新的更大的素數等等，其運算複雜性最終都將由為基本的乘法的運算速度決定。Van der Hoeven 認為，許多其他類型的問題理論上可以達到的最快的被解決的速度極限，最終也都將由乘法的運算速度決定。
「物理學中也有一些十分重要的常量，比如光速就是決定許多其他物理現象的基本參數，」Van der Hoeven 說，「如果你想知道計算機解決各種數學問題的速度有多快，那麼整數乘法的運算速度也將是回答這一問題的一個基本參數，描述計算機的許多種運算的速度都將會用到這個參數。」
大多數人所學乘法的運算方法都是以下這種方法。將兩個乘數排成兩行，用下面的乘數中的每一位數字分別去乘以上面的乘數的每一位數字，然後將所有的相乘結果相加。比如說，如果是兩個兩位數的乘法運算，你需要進行四次兩個一位數的相乘，然後將這四個相乘的結果相加。
這個我們在小學就學過的乘法的算法，即豎式計算乘法的方法，在進行 n 位數之間的相乘時，需要進行大約 n 的平方次個位數的相乘，這裡 n 是每個乘數的位數。所以，兩個三位數的乘法需要進行 9 次個位數的相乘，而如果你要進行的是兩個 100 位數的大數相乘，就需要 10,000 次個位數的相乘。
圖丨傳統的豎式計算方法（來源：網際網路）
上面說到的豎式計算方法，其實更適用於位數少的數字之間的相乘。當我們需要進行數百萬位數或數十億位數的乘數之間的相乘時，豎式計算方法就顯得無能為力了，例如計算圓周率或者尋找更大的質數。
如果要將兩個 10 億位數的數字相乘，需要進行十億的平方次個位數的相乘，這個運算需要現代計算機花費大約 30 年的時間。
在過去的數千年以來，人們都認為沒有比豎式計算方法更快的乘法的算法了。
直到 1960 年，一位名叫 Anatoly Karatsuba 的 23 歲的俄羅斯數學家參加了由 20 世紀最偉大的數學家之一 Andrey Kolmogorov 領導的研討會。當時，Kolmogorov 斷言，沒有一種方法可以以少於 n 的平方次個位數之間的相乘來完成兩個 n 位數之間的相乘。但是 Karatsuba 認為有；然後僅僅經過了一周的探索，他就找到了這種方法。
高能預警， Karatsuba 提出的算法思路如下 ：
計算25乘以63， 傳統的算法如下需要4次個位數之間的相乘以及幾次加法，如下：
Karatsuba 算法需要3次個位數之間的相乘以及幾次加法和減法，如下：
後者看似步驟比較多，但其優勢在特大數相乘時就顯現出來了，主要體現在節省個位數之間相乘的次數上：當乘數的位數很多時，可以重複進行 Karatsuba過程，將原來的乘數拆分成更小的部分。所進行的拆分的次數越多，相比傳統算法，你就節省了越多次個位數之間的相乘。
例如，計算 2531 乘以1467，傳統的算法需要進行 16 次個位數之間的相乘，如下：
而 Karatsuba 算法只需要進行 9 次個位數之間的相乘，如下：
（來源：quanta）
由此也可以看出，Karatsuba 的算法的主要想法是分治算法，也就是將大數的乘數分解成更小的部分，並以一種新穎的方式重新組合這些部分，這種方式可以用少量的加法和減法來代替大量的乘法。Karatsuba 算法節省了時間，因為這一運算僅需 2 的 n 次方次個位數的相乘，而不是之前的 n 的平方次。
賓夕法尼亞州立大學數學家 Martin Fürer 說道：「另外，比起豎式計算方法，你可以在學校裡提前一年學會這種方法，因為這種方法更容易，你可以在線性的時間內快速完成運算，這幾乎和從右到往左閱讀數字一樣快」。Martin Fürer 在 2007 年也創造了當時世界上最快的乘法算法。
在處理大數乘法時，可以重複進行 Karatsuba 過程，將原始數字拆分為幾乎與數字的位數一樣多個部分。通過每一次拆分，你都可以將本需要許多許多次的乘法以需要的運算次數少的加法和減法來替代。
新南威爾斯大學的數學家，同時也是這篇新論文的共同作者之一 David Harvey 說：「Karatsuba 算法可以把一些乘法變成加法，而對於計算機來說加法會更快。」
使用 Karatsuba 的方法，可以達到在 n 的 1.58 次方次個位數的乘法後，完成兩個 n 位數的乘數之間的相乘。然後在 1971 年，Arnold Schönhage 和 Volker Strassen 發表了一種能夠以 n×log n×log（log n）次個位數的相乘來完成大數相乘方法，其中 log n 是 n 的對數。而利用 Karatsuba 的方法進行兩個 10 億位數字之間的相乘時，則大約需要 165 萬億個額外的步驟。
（來源：此次論文）
Schönhage 和 Strassen 的大數相乘的算法，對之後的大數相乘算法的發展產生了兩個重要的長期影響。
首先，它頭一次在大數相乘領域將一種來自於信號處理技術領域的被稱為**快速傅立葉變換的方法引入了該領域。之後的每一次快速乘法算法都以這種方法為基礎。
另外一個重要影響是，在同一篇論文中，Schönhage 和 Strassen 推測道，應該有一個比他們所發現的算法更快的算法——一種只需要 n×log n 次運算的方法，而且這種算法將會是最快的算法。他們的推測主要是基於一種預感，因為他們覺得大數乘法的最少的基本操作次數應該比 n×log n×log（log n）這個公式更優雅。
「這其實是一種很普遍的共識，人們都認為既然乘法是一個如此重要的基本操作，那麼從美學的角度來看，這樣一個重要的操作需要一個很優雅的複雜性極限的描述公式，」Fürer 說，「從普遍經驗來看，最最基本的事物的數學描述總是十分優雅的。」
不過，在之後的 36 年裡，都沒有人找到比 Schönhage 和 Strassen 這個不那麼優雅的需要 n×log n×log（log n）次基本運算的算法更快的大數乘法的算法。
（來源：quanta）
直到 2007 年，Fürer 終於打破了這一領域一直沒有進展的狀態，而這次發現仿佛打開了人類這在一領域發現的閥門一般。在過去的十年中，數學家們不斷的相繼發現更快的乘法算法，而且每種算法都比之前更接近 n×log n，但是卻一直沒有完全達到它。直到上個月，Harvey 和 van der Hoeven 終於達到了。
他們的方法是對之前的主要方法的一種改進和優化。他們的方法也會分割數字，使用快速傅立葉變換的改進版本，而且他們還利用了過去四十年間這一領域其他進步的成果。van der Hoeven 說，「只不過我們以更激進的方式來使用快速傅立葉變換，我們的方法要進行多次快速傅立葉變換而不只是一次，而且也用加法和減法代替更多的乘法。」
Harvey 和 van der Hoeven 的算法證明了乘法可以進行 n×log n 次基本乘法來完成。但是，他們並不能證明沒有比這種方法更快的算法。要證明這種方法是最好的方法要比發現這一算法困難得多。2 月底，奧胡斯大學的一個計算機科學家小組發表了一篇論文，認為如果另一個未經證實的猜想成立的話，這一方法將可以被證實確實是乘法的最快的算法。
雖然這一新的算法理論上將有著重大意義，但實際上比起之前的算法，它其實並沒有進行太大的變化，它只比已經在被我們使用的算法稍微好一些。
「使用這種算法，最好的情況下也只比之前的算法最快三倍，」van der Hoeven 說。「這並沒有比之前快很多。」
此外，計算機硬體的設計也在過去幾年間發生了許多變化。二十年前，計算機執行加法要比乘法快很多。但是乘法和加法之間的運算速度的差距在過去 20 年中已經大大縮小，在某些晶片架構中，乘法甚至比加法更快。在使用某些硬體時，「你甚至可以讓計算機通過做多次乘法來提高加法的運算速度，這在之前簡直的不可想像的，」Harvey 說。
不過，硬體隨時間在不斷發展，但是對於一種運算的最佳算法的尋找卻是是永恆的沒有盡頭的。無論計算機在未來會變成怎樣，Harvey 和 van der Hoeven 的算法將一直會是最有效的乘法運算方法之一。
圖丨新算法的長圖版（來源：quanta）
圖書推薦：
基於Excel實踐，
直擊神經網絡根本原理
掃一掃，京東購
《深度學習的數學》
作者：湧井良幸，湧井貞美
譯者：楊瑞龍
書中基於豐富的圖示和具體示例，通俗地介紹了深度學習相關的數學基礎知識。第1章介紹神經網絡的概況；第2章介紹理解神經網絡所需的數學基礎知識；第3章介紹神經網絡的最優化；第4章介紹神經網絡和誤差反向傳播法；第5章介紹深度學習和卷積神經網絡。
菲爾茲獎得主陶哲軒數學思維大解析
掃一掃，京東購
《陶哲軒教你學數學》
作者：陶哲軒
譯者：李馨
本書論述解決數學問題時會涉及的各種策略、方法，旨在激發青少年對數學的興趣。書中涵蓋的內容包括：數論、代數、分析、歐幾裡得幾何、解析幾何。
亞馬遜原版4.8星，
陶哲軒的教學講義
掃一掃，京東購
《陶哲軒實分析》
作者：Terence Tao
譯者：李馨
本書主要介紹數學分析中的一些內容，以構造數系和集合論開篇，逐漸深入到級數、函數等高等數學內容，舉例詳實，每部分內容後的習題與正文內容密切相關，有利於讀者掌握所學的內容。本書在附錄部分還介紹了數理邏輯基礎和十進位，突出了嚴格性和基礎性。
本文轉載自：淺黑科技
題圖來源：Freepik.com