10億位超級大整數相乘僅需30秒,半個世紀的猜測終被證明

2020-12-12 騰訊網

　　新智元原創

　　來源：theconversation

　　編輯：金磊、小芹

　　【新智元導讀】自1971年以來，兩位數學科學家猜測，超級大整數相乘極限速度將是N log (N)，且無法被超越。近日，該猜測終於被實現：2個10億位超級大整數相乘，僅需30秒！

　　超級大整數相乘極限速度實現了！

　　整數相乘是每個人必學的一個運算，我們通常採用的思路是：第一個數字的n位乘以第二個數字的n位，這就意味著要進行n2次的乘法運算。但當這兩個整數大到一定程度時，這個過程的計算量是相當龐大且驚人的。

　　當然，前人們已經找到了一些解決方法來改善這一問題。早在1971年，兩位德國數學家就猜測，兩個大數相乘的可以達到一種令人難以置信的速度，即N log (N)。然而，這個聰明的想法幾十年來一直只是假設。

　　直到現在，這個假設終於被證明了！

　　澳大利亞新南威爾斯大學(UNSW)的數學家、副教授David Harvey近日聲稱，他和他的合著者首次破解了這個由Arnold Sch?nhage 和 Volker Strassen提出，存在近半個世紀之久的數學難題。

　　論文地址：

　　https://hal.archives-ouvertes.fr/hal-02070778/document

　　簡單來說，這項研究採用了1,729維快速傅立葉變換(FFT)，使得計算速度達到了N log (N)——目前理論上的極限值。

　　以前，兩個十億位的整數相乘，若是採用常規算法，大約需要幾個月才能算出它們的結果。但是應用該新算法，僅需30秒！

　　數學處處充滿驚喜，大數乘法速度屢破記錄，或已至極限

　　兩個整數相乘很簡單對吧？

　　小學的時候我們就學過如何做整數的乘法運算，例如：

　　但是，若是整數長度大到了一定程度，這種方法真的是最好的嗎？

　　在一般的乘法運算過程中，我們需要把第一個整數的每一位和第二個整數的每一位做乘法。如果這兩個數都有N位，那就是N2(或N x N)相乘。在上面的例子中，N是3，所以我們要做32= 9次乘法。

　　1956年前後，著名的蘇聯數學家安德烈·科爾莫戈羅夫(Andrey Kolmogorov)推測，這就是兩個整數相乘的最好方法。

　　換句話說，不管你怎麼安排計算，你要做的功至少與N2成正比。兩倍的數字意味著四倍的工作量。

　　科爾莫戈羅夫認為，如果有更簡便的方法，那肯定已經人們發現了，畢竟人類在「乘法」這件事兒上探索了千年之久。

　　被打臉，更快的方法誕生

　　然而，就在幾年後，科爾莫戈羅夫就被打臉了。

　　1960年，23歲的俄羅斯數學系學生阿納託利·卡拉蘇巴(Anatoly Karatsuba)發現了一種代數技巧，可以減少所需的乘法次數。

　　例如，要乘四位數的數，不需要42= 16的乘法，卡拉蘇巴的方法只需要9次。當使用他的方法時，兩倍的數字只意味著三倍的工作量。

　　而且隨著數字位數的增大，這種方法的有效性越發顯著，對於一千位數字的相乘，比之前的方法所需的乘法次數要少17倍。

　　大數字相乘在生活中的應用

　　有人會很好奇，誰會用到這麼大的數字來做乘法呢？事實上，現實生活中由大量的應用是需要這麼做的，最典型的就是密碼學。

　　每次我們在網際網路上進行加密通信時（例如，訪問銀行網站或執行網絡搜索），我們的設備都會執行的乘法次數是非常恐怖的，涉及數百甚至數千位的數字。

　　對於一些更深奧的應用程式，數學家必須處理更大的數字，數百萬、數十億甚至數萬億的數字。對於如此龐大的數字，即使是卡拉蘇巴的算法也是太慢了。

　　1971年，德國數學家阿諾德·紹哈格(Arnold Schonhage)和沃爾克·斯特拉森(Volker Strassen)的工作取得了真正的突破。他們解釋了如何使用快速傅立葉變換(FFT)來有效地對「大數字」做乘法。今天的數學家經常使用他們的方法來處理數十億位數的數字。

　　極限速度猜測

　　在他們1971年發表的論文中，他們也提到了一個驚人的猜測。

　　他們猜測的前半部分是，應該有可能使用最多與N log (N) (N乘以N的自然對數)成比例的一些基本運算來乘N位數字。但他們的算法並沒有達到這個理想的結果，速度慢了一個log因子(log N)。

　　而後的研究者們對此進行了不懈的深入挖掘，但直到2007年，Martin Furer的工作也只是接近N log (N)。

　　猜測的後半部分是，N log (N)應該就是速度的極限——沒有任何可能的乘法算法能做得比這個更好。

　　乘法運算速度極限已經實現？

　　就在前幾周，Joris van der Hoeven和David Harvey共同發表的一篇論文《Integer multiplication in time O(n log n)》描述了一種新的乘法算法，最終達到了N log(N)這一「聖杯」。

　　該算法突破性重點在於使用多維FFT，而不是僅僅使用一維FFT。自1971年以來，在很多領域都會涉及多維FFT的應用，例如JPEG格式圖像依賴於二維FFT，而三維FFT在物理和工程中有很多應用。

　　而在這篇論文中，所用到的FFT維度高達1,729。

　　但是，以目前的形式來看，新算法實際上並不實用，因為論文中給出的證明只適用於非常大的數字。即使每個數字都寫在氫原子上，在可觀測的宇宙中也幾乎沒有足夠的空間把它們寫下來。

　　另一方面，作者還希望通過進一步的改進，使得該算法可以應用於只有數十億或數萬億位數的數字。如果是這樣，它很可能成為計算數學家「軍火庫」中不可或缺的工具。

　　若Schonhage-Strassen猜想是正確的，那麼從理論的角度來看，新算法就是這條路的終點——不可能做得更好。

　　但論文作者也表示：「若猜想被證明是錯誤的，我會感到非常驚訝。但我們不應該忘記科爾莫戈羅夫的遭遇。」

　　畢竟，數學處處充滿驚喜。

　　作者簡介

　　David Harvey

　　新南威爾斯大學數學與統計學院副教授和ARC未來研究員。研究領域包括計算數論與算術幾何，多項式與整數算術。

　　所獲獎項：

　　2017–2021: Counting points on algebraic surfaces ($805,054)ARC Future Fellowship, FT160100219

　　2015–2017: Fast algorithms for zeta functions of algebraic varieties ($325,500)ARC Discovery Project, DP150101689

　　2012–2014: Counting solutions to equations over fields of large characteristic ($375,000)ARC Discovery Early Career Researcher Award, DE120101293

　　主頁地址：

　　https://web.maths.unsw.edu.au/~davidharvey/

　　Joris van der Hoeven

　　CNRS研究主任、MAX團隊組長。主要研究集中在漸近微積分和複分析的自動化，以及快速算法。

　　曾與Matthias Aschenbrenner合作共同出版了《漸近微分代數與變級數模型理論》一書，證明了漸近微分代數的量詞消去定理。另一個主要研究課題是具有特殊函數或更一般的微分方程解的複分析和計算的自動化。一方面，這導致了一些有趣的理論問題，如可計算性、零點測試、奇點等。另一方面，需要為多精度計算開發和實現快速、可靠和數值穩定的算法。

　　主頁地址：

　　http://www.texmacs.org/joris/main/joris.html

　　參考連結：

　　https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923

　　https://hal.archives-ouvertes.fr/hal-02070778/document

　　https://www.iflscience.com/editors-blog/newly-cracked-math-puzzle-allows-faster-multificaiton-of-large-numbers/

相關焦點

  • 最高效的乘法:迄今最快計算兩個非常大的數字相乘的算法!
    四千年前，巴比倫人發明了乘法，而最近數學家們又對乘法進行了完善，兩位研究人員描述了迄今為止發現的將兩個非常大的數字相乘的最快方法。這篇論文具有重要的意義，標誌著長期以來尋找最高效乘法步驟的努力達到了新的高度。
  • 最高效的乘法:兩個非常大的數字相乘迄今最快算法
    四千年前，巴比倫人發明了乘法，而最近數學家們又對乘法進行了完善，兩位研究人員描述了迄今為止發現的將兩個非常大的數字相乘的最快方法。這篇論文具有重要的意義，標誌著長期以來尋找最高效乘法步驟的努力達到了新的高度。
  • 用印度數學方法計算100～110之間整數的相乘
    印度數學的一些方法可以比我們一般的計算方法快10倍，學習了印度數學的人能夠在幾秒鐘內口算或心算出三四位數的複雜運算。而且，印度數學的方法簡單直接，即使是沒有數學基礎的人也能很快掌握它。它還非常有趣，運算過程就像遊戲一樣令人著迷。
  • 一顆顆璀璨的正整數中的數字珍珠,極具挑戰的難題
    17世紀「神數術」大師龐格斯在一本洋洋700頁的巨著《數的玄學》中，一口氣列出了28個所謂「完美數」，他是在塔塔利亞給出的20個的基礎上補充了8個。可惜兩人都沒有給出證明和運算過程，後人發現其中有許多是錯誤的。
  • 246位超級散戶「爆倉」!10倍槓桿以上投資者最高損失7000萬!幣圈...
    9月25日凌晨2點45分，比特幣在毫無徵兆的情況下一路大跌超過15%，盤中一度跌破8000美元整數關口，創下6月以來最低點7944.33美元，進而引發整個虛擬貨幣的「大崩盤」，連帶的是無數爆倉的帳戶，整個幣圈一片哀嚎。
  • 超級神秘的完全數,魅力無窮,千年不朽的探尋之旅
    更驚喜的是，如果一個正整數全部因子（包括它本身）之和等於這個數的某個整數倍，我們就稱這個數為多完全數。如120全部因子為1，2，3，4，5，6，8，10，12，15，20，24，30，40，60，120。這些因子之和為360，360正好是120的三倍。
  • 小學數學基礎概念歸納總結:整數篇
    一，十，百，千，萬，十萬，百萬，千萬，億.都叫做計數單位。每相鄰的兩個計數單位間的進率是十。這種計數方法叫做十進位計數法。寫數的時候，把計數單位按照一定的順序排列起來，它們所佔的位置叫做數位。一個數字所在的數位不同，表示的數的大小也不同。第一個數位稱為個位，依次是十位，百位，千位，萬位，十萬位.
  • 超級電池比它快1000倍,充滿電僅需15秒!
    超級電池比它快1000倍，充滿電僅需15秒！大家都知道，目前新能源已經運用到了我們的生活當中，而其中電動汽車就是其中的突出代表，電動汽車利用電池驅動。一般我們經常使用的電池就是鋰電池，作為目前電池使用的主流，鋰電池其實擁有許多的缺陷，因為材料問題，當出現充電過度、短路等問題時，電池熱量會上升，就會引起爆炸、自燃等現象。
  • 面試官:100個3相乘個位數是多少?博士小夥子10秒快速算出答案!
    面試官：100個3相乘個位數是多少？博士小夥子10秒快速算出答案！不同的行業有不一樣的思維，面試官會根據自身行業的特點，設計出別有一番特色的面試題。這是一家大企舉辦的招聘會面試現場，前來求職的人全是有著真材實料的優秀人才，其中還有不少的博士文憑的高端人才，阿傑就是其中的一名。阿傑從小到大一直都是老師眼中的乖寶寶，家長口中那個別人家的孩子，阿傑在學業上面也一直都沒有令人失望，一路順風順水的拿到了博士的學位，而阿傑在畢業後就拿著簡歷投遞了這家有名的大公司，來到了面試的現場。
  • 最長數學證明破解世界難題:看完需要100億年
    近日，一個由美英兩國三位數學家組成的研究團隊宣稱他們應該得到這筆獎金。但是，數學同行們發現，這個研究團隊所得出的結論同樣也很難驗證，因為他們是利用超級計算機證明出來的，證明的過程非常複雜，堪稱世界最長的數學證明，閱讀全部的證明文件需要花費100億年。
  • 評審8年終獲發表,數學天才望月新一證明abc猜想,全球只有十幾個...
    大概如下：有三個互質正整數a、b、c，且c=a+b。所謂互質，即它們的最大公約數是1。因此8 + 9 = 17、5 + 16 = 21是符合條件的一組數字，但是6 + 9 = 15不是。接著，我們把abc的質因數都提取出來，比如5、16、21的質因數是5、2、3、7，這些質因數相乘的結果為210，這個數比原來的三個數大得多。又比如5、27、32，它們的質因數是5、3、2，相乘結果為30，就比32小。但第二種情形極為罕見。
  • 數字裡的超級黃金搭檔,梅森素數和完全數
    1792年，15歲的高斯無聊時候翻了翻前1000以內的素數表，統計了一下大概個數，就得出了一個素數分布規律。這就是素數定理，雖然稱為素數定理，但是當年高斯並沒有給出證明。這個定理的證明直到19世紀末才有人完整給出。
  • 超級好聽的兒歌收藏起來!
    多位數改寫歌萬位後面「0」去掉，加上萬字改完了。億位後面「0」去掉，加個億字就改好。億級萬級仿個級，讀完後面加單位。一級一級往下寫，珠不靠梁0佔位。多位數的大小比較多位數大小看位數，位數多的數就大；位數相同看高位，高位數大數就大。
  • MATLAB整數類型
    整數的類型、長度和取值範圍數據類型取值範圍轉換函數有符號 8 位整數-27 ~ -27 - 1int8()有符號 16 位整數-215 ~ -215 - 1int16()有符號 32 位整數-231 ~ -231 - 1int32()有符號 64 位整數-263 ~ -263 - 1int64()無符號 8 位整數0 ~ 28 - 1uint8()無符號 16 位整數0 ~
  • 2名數學家或發現史上最快超大乘法運算法,欲破解困擾人類近半個世紀的問題
    這篇論文的誕生，也意味著數學界最基本的運算方式又有了更新更有效的運算過程，有望破解了一個已經存在近半個世紀的數學問題。將兩個乘數排成兩行，用下面的乘數中的每一位數字分別去乘以上面的乘數的每一位數字，然後將所有的相乘結果相加。比如說，如果是兩個兩位數的乘法運算，你需要進行四次兩個一位數的相乘，然後將這四個相乘的結果相加。
  • 小學數學基礎概念歸納總結①:整數篇
    一，十，百，千，萬，十萬，百萬，千萬，億.都叫做計數單位。每相鄰的兩個計數單位間的進率是十。這種計數方法叫做十進位計數法。寫數的時候，把計數單位按照一定的順序排列起來，它們所佔的位置叫做數位。一個數字所在的數位不同，表示的數的大小也不同。第一個數位稱為個位，依次是十位，百位，千位，萬位，十萬位.
  • 小學數學——基礎概念歸納總結①:整數篇
    一，十，百，千，萬，十萬，百萬，千萬，億.都叫做計數單位。每相鄰的兩個計數單位間的進率是十。這種計數方法叫做十進位計數法。寫數的時候，把計數單位按照一定的順序排列起來，它們所佔的位置叫做數位。一個數字所在的數位不同，表示的數的大小也不同。第一個數位稱為個位，依次是十位，百位，千位，萬位，十萬位.
  • 小升初銜接整數的基本概念
    （一）整數 　　1 整數的意義 　　自然數和0都是整數。 　　2 自然數 　　我們在數物體的時候，用來表示物體個數的1，2，3……叫做自然數。 　　一個物體也沒有，用0表示。0也是自然數。 　　3計數單位 　　一（個）、十、百、千、萬、十萬、百萬、千萬、億……都是計數單位。 　　每相鄰兩個計數單位之間的進率都是10。這樣的計數法叫做十進位計數法。
  • 數學天才望月新一證明abc猜想,只有十幾個數學家能懂
    大概如下：有三個互質正整數a、b、c，且c=a+b。所謂互質，即它們的最大公約數是1。因此8 + 9 = 17、5 + 16 = 21是符合條件的一組數字，但是6 + 9 = 15不是。接著，我們把abc的質因數都提取出來，比如5、16、21的質因數是5、2、3、7，這些質因數相乘的結果為210，這個數比原來的三個數大得多。
  • 評審8年終獲發表,數學天才望月新一證明abc猜想,全球只有十幾個數學家讀懂但爭議未消
    大概如下：有三個互質正整數a、b、c，且c=a+b。所謂互質，即它們的最大公約數是1。因此8 + 9 = 17、5 + 16 = 21是符合條件的一組數字，但是6 + 9 = 15不是。接著，我們把abc的質因數都提取出來，比如5、16、21的質因數是5、2、3、7，這些質因數相乘的結果為210，這個數比原來的三個數大得多。又比如5、27、32，它們的質因數是5、3、2，相乘結果為30，就比32小。但第二種情形極為罕見。如果a和b都是小於100的數，我們能找到3044個符合條件的abc組合，其中只有7組滿足第二種情形。