0
  • 聊天消息
  • 系統(tǒng)消息
  • 評(píng)論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會(huì)員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識(shí)你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

該猜測(cè)終于被實(shí)現(xiàn):2個(gè)10億位超級(jí)大整數(shù)相乘,僅需30秒!

DPVg_AI_era ? 來(lái)源:lp ? 2019-04-19 14:02 ? 次閱讀

自1971年以來(lái),兩位數(shù)學(xué)科學(xué)家猜測(cè),超級(jí)大整數(shù)相乘極限速度將是N log (N),且無(wú)法被超越。近日,該猜測(cè)終于被實(shí)現(xiàn):2個(gè)10億位超級(jí)大整數(shù)相乘,僅需30秒!

超級(jí)大整數(shù)相乘極限速度實(shí)現(xiàn)了!

整數(shù)相乘是每個(gè)人必學(xué)的一個(gè)運(yùn)算,我們通常采用的思路是:第一個(gè)數(shù)字的n位乘以第二個(gè)數(shù)字的n位,這就意味著要進(jìn)行n2次的乘法運(yùn)算。但當(dāng)這兩個(gè)整數(shù)大到一定程度時(shí),這個(gè)過(guò)程的計(jì)算量是相當(dāng)龐大且驚人的。

當(dāng)然,前人們已經(jīng)找到了一些解決方法來(lái)改善這一問(wèn)題。早在1971年,兩位德國(guó)數(shù)學(xué)家就猜測(cè),兩個(gè)大數(shù)相乘的可以達(dá)到一種令人難以置信的速度,即N log (N)。然而,這個(gè)聰明的想法幾十年來(lái)一直只是假設(shè)。

直到現(xiàn)在,這個(gè)假設(shè)終于被證明了!

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

論文地址:

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

簡(jiǎn)單來(lái)說(shuō),這項(xiàng)研究采用了1,729維快速傅里葉變換(FFT),使得計(jì)算速度達(dá)到了N log (N)——目前理論上的極限值。

以前,兩個(gè)十億位的整數(shù)相乘,若是采用常規(guī)算法,大約需要幾個(gè)月才能算出它們的結(jié)果。但是應(yīng)用該新算法,僅需30秒!

數(shù)學(xué)處處充滿驚喜,大數(shù)乘法速度屢破記錄,或已至極限

兩個(gè)整數(shù)相乘很簡(jiǎn)單對(duì)吧?

小學(xué)的時(shí)候我們就學(xué)過(guò)如何做整數(shù)的乘法運(yùn)算,例如:

但是,若是整數(shù)長(zhǎng)度大到了一定程度,這種方法真的是最好的嗎?

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

1956年前后,著名的蘇聯(lián)數(shù)學(xué)家安德烈·科爾莫戈羅夫(Andrey Kolmogorov)推測(cè),這就是兩個(gè)整數(shù)相乘的最好方法。

換句話說(shuō),不管你怎么安排計(jì)算,你要做的功至少與N2成正比。兩倍的數(shù)字意味著四倍的工作量。

科爾莫戈羅夫認(rèn)為,如果有更簡(jiǎn)便的方法,那肯定已經(jīng)人們發(fā)現(xiàn)了,畢竟人類在“乘法”這件事兒上探索了千年之久。

被打臉,更快的方法誕生

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

1960年,23歲的俄羅斯數(shù)學(xué)系學(xué)生阿納托利·卡拉蘇巴(Anatoly Karatsuba)發(fā)現(xiàn)了一種代數(shù)技巧,可以減少所需的乘法次數(shù)。

例如,要乘四位數(shù)的數(shù),不需要42 = 16的乘法,卡拉蘇巴的方法只需要9次。當(dāng)使用他的方法時(shí),兩倍的數(shù)字只意味著三倍的工作量。

而且隨著數(shù)字位數(shù)的增大,這種方法的有效性越發(fā)顯著,對(duì)于一千位數(shù)字的相乘,比之前的方法所需的乘法次數(shù)要少17倍。

大數(shù)字相乘在生活中的應(yīng)用

有人會(huì)很好奇,誰(shuí)會(huì)用到這么大的數(shù)字來(lái)做乘法呢?事實(shí)上,現(xiàn)實(shí)生活中由大量的應(yīng)用是需要這么做的,最典型的就是密碼學(xué)。

每次我們?cè)诨ヂ?lián)網(wǎng)上進(jìn)行加密通信時(shí)(例如,訪問(wèn)銀行網(wǎng)站或執(zhí)行網(wǎng)絡(luò)搜索),我們的設(shè)備都會(huì)執(zhí)行的乘法次數(shù)是非??植赖模婕皵?shù)百甚至數(shù)千位的數(shù)字。

對(duì)于一些更深?yuàn)W的應(yīng)用程序,數(shù)學(xué)家必須處理更大的數(shù)字,數(shù)百萬(wàn)、數(shù)十億甚至數(shù)萬(wàn)億的數(shù)字。對(duì)于如此龐大的數(shù)字,即使是卡拉蘇巴的算法也是太慢了。

1971年,德國(guó)數(shù)學(xué)家阿諾德·紹哈格(Arnold Schonhage)和沃爾克·斯特拉森(Volker Strassen)的工作取得了真正的突破。他們解釋了如何使用快速傅里葉變換(FFT)來(lái)有效地對(duì)“大數(shù)字”做乘法。今天的數(shù)學(xué)家經(jīng)常使用他們的方法來(lái)處理數(shù)十億位數(shù)的數(shù)字。

極限速度猜測(cè)

在他們1971年發(fā)表的論文中,他們也提到了一個(gè)驚人的猜測(cè)。

他們猜測(cè)的前半部分是,應(yīng)該有可能使用最多與N log (N) (N乘以N的自然對(duì)數(shù))成比例的一些基本運(yùn)算來(lái)乘N位數(shù)字。但他們的算法并沒有達(dá)到這個(gè)理想的結(jié)果,速度慢了一個(gè)log因子(log N)。

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

猜測(cè)的后半部分是,N log (N)應(yīng)該就是速度的極限——沒有任何可能的乘法算法能做得比這個(gè)更好。

乘法運(yùn)算速度極限已經(jīng)實(shí)現(xiàn)?

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

該算法突破性重點(diǎn)在于使用多維FFT,而不是僅僅使用一維FFT。自1971年以來(lái),在很多領(lǐng)域都會(huì)涉及多維FFT的應(yīng)用,例如JPEG格式圖像依賴于二維FFT,而三維FFT在物理和工程中有很多應(yīng)用。

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

但是,以目前的形式來(lái)看,新算法實(shí)際上并不實(shí)用,因?yàn)檎撐闹薪o出的證明只適用于非常大的數(shù)字。即使每個(gè)數(shù)字都寫在氫原子上,在可觀測(cè)的宇宙中也幾乎沒有足夠的空間把它們寫下來(lái)。

另一方面,作者還希望通過(guò)進(jìn)一步的改進(jìn),使得該算法可以應(yīng)用于只有數(shù)十億或數(shù)萬(wàn)億位數(shù)的數(shù)字。如果是這樣,它很可能成為計(jì)算數(shù)學(xué)家“軍火庫(kù)”中不可或缺的工具。

若Schonhage-Strassen猜想是正確的,那么從理論的角度來(lái)看,新算法就是這條路的終點(diǎn)——不可能做得更好。

但論文作者也表示:“若猜想被證明是錯(cuò)誤的,我會(huì)感到非常驚訝。但我們不應(yīng)該忘記科爾莫戈羅夫的遭遇?!?/p>

畢竟,數(shù)學(xué)處處充滿驚喜。

作者簡(jiǎn)介

David Harvey

新南威爾士大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院副教授和ARC未來(lái)研究員。研究領(lǐng)域包括計(jì)算數(shù)論與算術(shù)幾何,多項(xiàng)式與整數(shù)算術(shù)。

所獲獎(jiǎng)項(xiàng):

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

主頁(yè)地址:

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

Joris van der Hoeven

CNRS研究主任、MAX團(tuán)隊(duì)組長(zhǎng)。主要研究集中在漸近微積分和復(fù)分析的自動(dòng)化,以及快速算法。

曾與Matthias Aschenbrenner合作共同出版了《漸近微分代數(shù)與變級(jí)數(shù)模型理論》一書,證明了漸近微分代數(shù)的量詞消去定理。另一個(gè)主要研究課題是具有特殊函數(shù)或更一般的微分方程解的復(fù)分析和計(jì)算的自動(dòng)化。一方面,這導(dǎo)致了一些有趣的理論問(wèn)題,如可計(jì)算性、零點(diǎn)測(cè)試、奇點(diǎn)等。另一方面,需要為多精度計(jì)算開發(fā)和實(shí)現(xiàn)快速、可靠和數(shù)值穩(wěn)定的算法。

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題,請(qǐng)聯(lián)系本站處理。 舉報(bào)投訴
  • 算法
    +關(guān)注

    關(guān)注

    23

    文章

    4623

    瀏覽量

    93104
  • 傅里葉變換
    +關(guān)注

    關(guān)注

    6

    文章

    442

    瀏覽量

    42651

原文標(biāo)題:極限速度!10億位超級(jí)大整數(shù)相乘僅需30秒,半個(gè)世紀(jì)的猜測(cè)終被證明

文章出處:【微信號(hào):AI_era,微信公眾號(hào):新智元】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

收藏 人收藏

    評(píng)論

    相關(guān)推薦

    鴻蒙原生應(yīng)用元服務(wù)開發(fā)-倉(cāng)頡基礎(chǔ)數(shù)據(jù)類型整數(shù)類型

    范圍為:。下表列出了所有整數(shù)類型的表示范圍: 程序具體使用哪種整數(shù)類型,取決于程序中需要處理的整數(shù)的性質(zhì)和范圍。在 Int64 類型適合的情況下,首選 Int64 類型,因?yàn)?Int
    發(fā)表于 09-13 14:55

    RISC-V基礎(chǔ)整數(shù)指令集

    。 ARM-32指令集12的立即字段不僅僅是一個(gè)常量,而是一個(gè)函數(shù)的輸入,此函數(shù)根據(jù)12立即數(shù)的輸入來(lái)產(chǎn)生一個(gè)常量:8
    發(fā)表于 07-27 22:25

    ADS1204 4個(gè)110MHz、2階、Δ-Σ調(diào)制器數(shù)據(jù)表

    電子發(fā)燒友網(wǎng)站提供《ADS1204 4個(gè)1、10MHz、2階、Δ-Σ調(diào)制器數(shù)據(jù)表.pdf》資料免費(fèi)下載
    發(fā)表于 07-26 09:48 ?0次下載
    ADS1204 4<b class='flag-5'>個(gè)</b>1<b class='flag-5'>位</b>、<b class='flag-5'>10</b>MHz、<b class='flag-5'>2</b>階、Δ-Σ調(diào)制器數(shù)據(jù)表

    RV32I 基本整數(shù)指令集(2.0版本)簡(jiǎn)介

    用于實(shí)現(xiàn)對(duì)小的運(yùn)行時(shí)庫(kù)的快速調(diào)用。 條件分支 所有分支指令使用SB類指令格式。12B立即數(shù)編碼了以2字節(jié)倍數(shù)的有符號(hào)偏移量, 并加到當(dāng)前pc上,生成目標(biāo)地址。條件分支范圍是±4KB
    發(fā)表于 06-24 17:27

    氣密性檢測(cè)設(shè)備等30的意義是什么

    氣密性檢測(cè)設(shè)備做為工業(yè)制造行業(yè)的關(guān)鍵設(shè)備,用于檢測(cè)產(chǎn)品是否具有較好的密封性,以確保產(chǎn)品質(zhì)量和生產(chǎn)安全。使用這種設(shè)備的過(guò)程中,我們通常發(fā)覺設(shè)備在測(cè)試上有一段等待時(shí)長(zhǎng),其中常見的是等待30。那樣,為何氣密性檢測(cè)設(shè)備必須等待這30
    的頭像 發(fā)表于 06-13 13:53 ?264次閱讀
    氣密性檢測(cè)設(shè)備等<b class='flag-5'>30</b><b class='flag-5'>秒</b>的意義是什么

    十五充滿電并循環(huán)逆天神器 什么是超級(jí)電容器??

    )彼此分開。一個(gè)電容器不會(huì)同時(shí)使用所有三種介電材料,而只會(huì)使用其中一種。超級(jí)電容器使用不同的電介質(zhì)材料?;钚蕴渴窃?b class='flag-5'>超級(jí)電容器的兩個(gè)電極之間形成屏障的。
    的頭像 發(fā)表于 06-04 09:40 ?498次閱讀
    十五<b class='flag-5'>秒</b>充滿電并循環(huán)逆天神器 什么是<b class='flag-5'>超級(jí)</b>電容器??

    AD630可以用作這種乘法器嗎?怎么使用AD630實(shí)現(xiàn)個(gè)信號(hào)相乘呢?

    AD630芯片可以用作這種乘法器嗎?怎么使用AD630芯片實(shí)現(xiàn)個(gè)信號(hào)相乘呢?
    發(fā)表于 05-30 08:26

    10,一次性完成210個(gè)讀碼任務(wù)

    在工業(yè)生產(chǎn)中,生產(chǎn)商常常需要對(duì)生產(chǎn)的時(shí)間地點(diǎn)、焊料溫度、元件批號(hào)和測(cè)試數(shù)據(jù)等生產(chǎn)信息進(jìn)行編碼,形成二維碼印在物料上;在電子行業(yè)中,PCB線路板上的二維碼往往非常小,但由于生產(chǎn)過(guò)程中的質(zhì)檢、追溯等需求,需要在較大的視野范圍內(nèi)快速準(zhǔn)確地讀取這些碼。類似需求的場(chǎng)景非常多,本期小明就來(lái)分享明治智能讀碼器在大視野托盤讀碼場(chǎng)景中的應(yīng)用~檢測(cè)需求移動(dòng)讀取托盤上的DM碼選型
    的頭像 發(fā)表于 05-07 08:24 ?375次閱讀
    <b class='flag-5'>僅</b><b class='flag-5'>需</b><b class='flag-5'>10</b><b class='flag-5'>秒</b>,一次性完成210<b class='flag-5'>個(gè)</b>讀碼任務(wù)

    谷歌計(jì)劃投資30美元建數(shù)據(jù)中心

    谷歌公司近日宣布了一項(xiàng)雄心勃勃的投資計(jì)劃,將斥資30美元用于建設(shè)和擴(kuò)展其數(shù)據(jù)中心園區(qū)。其中,弗吉尼亞州的數(shù)據(jù)中心將追加10美元的投資,用于擴(kuò)建現(xiàn)有的三
    的頭像 發(fā)表于 05-06 11:30 ?568次閱讀

    傳特斯拉馬斯克將在印度公布20-30美元投資

    特斯拉(Tesla)CEO馬斯克(Elon Musk)將于下周訪問(wèn)印度,兩知情人士稱,馬斯克將在訪問(wèn)印度期間,宣布投資2030美元在當(dāng)?shù)亟ㄔO(shè)新工廠。
    的頭像 發(fā)表于 04-22 11:25 ?920次閱讀

    基于FPGA的并行ADC與DAC Verilog實(shí)現(xiàn)案例

    轉(zhuǎn)換的依據(jù)是一個(gè)簡(jiǎn)單的運(yùn)算關(guān)系:“補(bǔ)碼的整數(shù)值”+“原碼絕對(duì)值的整數(shù)值”=2^B,B為寬。比如帶符號(hào)數(shù)原碼1110的補(bǔ)碼為1010:111
    發(fā)表于 03-21 12:19 ?2511次閱讀
    基于FPGA的并行ADC與DAC Verilog<b class='flag-5'>實(shí)現(xiàn)</b>案例

    IIS328DQ響應(yīng)滯后5~30是什么原因造成的?

    水平放置,移動(dòng)為垂直放置,傳感器需要延遲5~30+后,傳感器的加速度數(shù)據(jù)才會(huì)變化。請(qǐng)問(wèn)這是正常指標(biāo)嗎?還是哪個(gè)地方未正確操作。 采用IIC總線,每1讀取一次傳感器加速度數(shù)據(jù)(XY
    發(fā)表于 03-21 07:48

    Adobe提出DMV3D:3D生成只需30!讓文本、圖像都動(dòng)起來(lái)的新方法!

    因此,本文研究者的目標(biāo)是實(shí)現(xiàn)快速、逼真和通用的 3D 生成。為此,他們提出了 DMV3D。DMV3D 是一種全新的單階段的全類別擴(kuò)散模型,能直接根據(jù)模型文字或單張圖片的輸入,生成 3D NeRF。在單個(gè) A100 GPU 上,
    的頭像 發(fā)表于 01-30 16:20 ?897次閱讀
    Adobe提出DMV3D:3D生成只需<b class='flag-5'>30</b><b class='flag-5'>秒</b>!讓文本、圖像都動(dòng)起來(lái)的新方法!

    激光焊接機(jī)如何實(shí)現(xiàn)高精度焊接

    激光,具有極短的脈沖寬度和高峰值功率。這種激光能夠產(chǎn)生極小的光斑,實(shí)現(xiàn)精確的能量集中,從而減少熱影響區(qū),提高焊接精度。2.精確的控制系統(tǒng):納激光焊接機(jī)配備了先進(jìn)的
    的頭像 發(fā)表于 01-29 15:38 ?1017次閱讀
    納<b class='flag-5'>秒</b>激光焊接機(jī)如何<b class='flag-5'>實(shí)現(xiàn)</b>高精度焊接

    Firefox長(zhǎng)達(dá)21年的 “陳年老bug”,終于修復(fù)了!

    Firefox 的工單記錄頁(yè)面顯示,一個(gè)在 21 年前發(fā)現(xiàn)的 bug 終于修復(fù)了。
    的頭像 發(fā)表于 01-25 11:08 ?432次閱讀
    Firefox長(zhǎng)達(dá)21年的 “陳年老bug”,<b class='flag-5'>終于</b><b class='flag-5'>被</b>修復(fù)了!