數學家找到了理論上最快的大數乘法演算法
諸位或許聽說過，計算機在執行加法運算的時候，幾乎可以瞬間給出答案。但是將兩個數字相乘，特別當數位超過十億時，那就得可一會兒了。
我們從小學裡學到的進位豎式長乘法步驟，對於非常大的數字相乘，會過於費時而無法使用。現在，有來自澳大利亞和法國的兩位數學家表示，他們已經找到了理論上最快的乘法演算法。
兩人聲稱已經實現了乘法演算法的優化上限——這一極限在差不多半個世紀前被首次提出。3月18日HAL文檔檔案網站通報了他們的結果，目前論文尚未通過同行評審。
如果問普通人對數學家的理解，「他們可能會說，"哦，他們坐在辦公室里，運算特別大的數字，"」悉尼新南威爾士大學的共同作者David Harvey開玩笑說，「對我來說，這是真的。」
在使用若干大數字進行數學運算時，要考慮所需操作的數量，以及進行計算所需的時間。數字位數增長時，計算時間也會增加。一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),存在一個正常數c使得fn*c>=T(n)恆成立。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。
雖然效率很低，但長乘法演算法實際上是我們在20世紀60年代以前最先進的乘法演算法，直到俄羅斯數學家Anatoly Karatsuba發現更優化的演算法。
十年後，一對德國數學家又取得了突破：Sch?nhage-Strassen演算法。它暗示——但從未證明——還存在進一步改進的空間。
「他們預測應該存在一種演算法，它的複雜度基本上為nlog(n)。」Harvey解釋道，「我們的論文給出了達成這一目標的首個演算法示例。」
根據研究人員的說法，通過長乘法將兩個十億位數相乘可能需要幾個月的計算時間。
使用Sch?nhage-Strassen演算法，則不到30秒，並且憑藉他們的新理論證明，理論上會更快——甚至可能是理論上最快的乘法演算法。
「從這個意義上講，我們的工作預計將為大數乘法問題畫上句號，儘管我們還不知道如何嚴格證明這一點。」Harvey說，「近50年來，人們一直在尋找這樣的演算法。人類最終會成功，這並不是一個荒謬的結論。」
值得注意的是，新演算法只能用在非常大的數字相乘時。具體有多大？
「我們也不知道，」研究人員在常見的Q&A環節中承認，儘管他們在論文中給出的一個示例用到了10214857091104455251940635045059417341952，這是一個非常非常非常大的數字。
雖然還未通過最終的審核，但他們的論文已經在世界數學界掀起波瀾。
賓夕法尼亞州立大學的理論計算機科學家Martin Fürer告訴《科學新聞》：「我對此感到非常驚訝。」
十多年前，Fürer本人試圖改進Sch?nhage-Strassen演算法，但最終放棄了，「我感覺毫無希望。」
Fürer說，它或許具有實際用途。巨大數字的乘法演算法對於某些具體的計算工作來說是非常有用的，如尋找新的素數。
即使這種方法缺少廣泛的應用，但它仍然是一項巨大的成就。
「如果結果是正確的，這是計算複雜性理論的一項重大成就。」來自INRIA Bordeaux和InstitutdeMathématiquesdeBordeaux的數學家和計算機科學家Fredrik Johansson告訴《新科學家》。
Harvey告訴AAP說：「反覆驗證讓我們確信它真是正確的，我仍然害怕它可能有錯誤。」
論文預印本可在HAL open access archive上獲得。
結合了sciencenews上的報道
本文譯自 sciencealert，由譯者 majer 基於創作共用協議(BY-NC)發布。
TAG:煎蛋 |