| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 31034 人关注过本帖
标题:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
只看楼主 加入收藏
wds1
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:49
帖 子:393
专家分:2025
注 册:2016-3-10
收藏
得分:0 
对于大数运算的算法,建议考虑位长和变量类型时,在参考java的系统算法(摘取):

1、Java 7 里面,就是用二重循环直接乘的,复杂度为O(n^2)。源代码:[BigInteger - Java71] (见1165行)
2、Java 8 里面,根据两个因数的大小,有三种乘法。源代码:[BigInteger - Java8] (见1464行):
   2.1、当两个因数均小于 2^(32 × 80)时,用二重循环直接相乘,复杂度为 O(n^2)
   2.2、当两个因数均小于 2^(32 × 240)时,采用 Karatsuba algorithm,复杂度为 O(n^(log2 3)≈O(n^1.585)
   2.3、否则,采用 Toom-Cook multiplication,其复杂度为 O( n^(log3 5) ≈ O(n^1.465)
3、根据java系统的算法分析,如果4096以下优选算法1、4096-8192的优选算法2、大于8192的优选算法3
2021-04-12 11:07
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 281楼 wds1
额,谢谢!
Karatsuba algorithm和Toom-Cook multiplication是啥?我不会,勉强算是弄出来快速傅里叶变换的乘法程序,和分治法乘法程序。
2021-04-12 16:41
wds1
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:49
帖 子:393
专家分:2025
注 册:2016-3-10
收藏
得分:0 
Karatsuba和Toom-Cook都是分治算法,只不过第一个是简单的分治算法
 
Karatsuba的原理:
  1、2位数乘法(ac,高位,bd低位):ab*cd=(a*10+b)*(c*10+d)=ac*100+(a*d+b∗c)*10+bd
  只要计算ac, bd, (a+b)*(c+d)三个数值,之后ac后面补2个0,bd不补,(a+b)*(c+d)后面补1个0
  2、3,4位数乘法(ac,高位,bd低位):
    ab*cd=(a*100+b)*(c*100+d)=ac*10000+(a*d+b∗c)*100+bd,与上面相比就是补的0不一样
  
   以上算法向当时把乘积位减半运算,如果是16位数的乘法一样适用。。
  
2021-04-12 17:32
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 283楼 wds1
额,谢谢!明白了一点,我用的分治法怎么不能提高速度反而降低了?
2021-04-12 18:14
wds1
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:49
帖 子:393
专家分:2025
注 册:2016-3-10
收藏
得分:0 
分治的核心是降低运算次数,但还有一点,那就是你的拆分是否合理。

例如:8000字节的10进制数据
1、如果将10进制转为16进制,那么大约可以减少2000字节的乘法运算量
1、拆分为8000个byte,那么n是8000,乘法计算量为O(8000^2)
2、拆分为4000个integer,  那么n是4000,乘法计算量为O(4000^2)
3、差分为2000个long,那么n是2000,,乘法计算量为O(2000^2)

另外,大数算法还和编程语言有关,对于支持大数数据类型和运算的系统速度就会快,因为他有专用的大数函数。


[此贴子已经被作者于2021-4-12 21:22编辑过]

2021-04-12 18:54
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 285楼 wds1
谢谢!我不会用16进制的算法,您的方法我还要好好学习,非常感谢!
我再看看前面的程序如何优化和修改,哈哈,学到不少,谢谢!
2021-04-12 20:47
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
高手编程的暴力乘法程序,就是快,下面是运行结果:

51750801837147361345408953922231823615475578427966187002956389087112242842559611794590895524485015222232340190036677951157401229518412775512617768569186939216558814320044037671525512763073762127357272238470370174050144130962253437215369727381909754581075278888137687950749577751967083233227932391898438489520107788418593104216764745143648165875043861634459264809523254076330115365651752264033578829280651927862062277153553168278640509846511729608378923480331705134467105387853440058108864733429085916392927954109944314725590758950098556991513109760871599045355054258610189920009222629391227784118536578933067532162200768112408111142115021110731900107445187734955403922470144187293970602024056652942406064101184615113779243566842311336047149767396006622923831778833173731302325162741660053390002572456069410383734906953419854919650114722834689335022576764661864630532595250136417800041415827379233503655173380741283758557001102498493237113089198106283487003030225058520047964863929279622015825870972146222540614667928697270131499340362072956956518213266361286372027834000838185920579641835952404678850816456467012890793914108776148483471455515695596694573035435841962871983614397882366460940068418989292218104650923374259244879331938925143014431488635252724366437874702141802712286424754174951797598162531093933772708024046029028652425912112434874797404878317364682580259997737809632860143160557722236459697738869857870982308547756781808568834445404196611833859447257611721058384661943492980180884154939581533269700568975940675513953240040220315659784214936947443784598154082110443748171557676558299300252057475022409541083454882202785077569281268346332901357829843950754331120530978456454396022570647840977328115888711408099894489014427119253061839770890965114853246067272044090282103668762164047374624856119676063310166566519499552342907590495696658359542582469176737197423550084705962160477441546453931948920780829433665262356431973422034925001341330921812806939990688094288773216182971976433480031438271163051341645350474631300965486818841553843112688792803367397276204832936049162335586140151875524537720425345701193713093955432559579831822084761702059241698184717469616732582600658006352069963017377661059372648121969448644394344799369193952197519795756182552461838014896498816263546256621347748100920475049252091842372001283217811864786225692344297842649982716736752004086642881662614773154743879410328420184057019873899911520017723788801*
 51750801837147361345408953922231823615475578427966187002956389087112242842559611794590895524485015222232340190036677951157401229518412775512617768569186939216558814320044037671525512763073762127357272238470370174050144130962253437215369727381909754581075278888137687950749577751967083233227932391898438489520107788418593104216764745143648165875043861634459264809523254076330115365651752264033578829280651927862062277153553168278640509846511729608378923480331705134467105387853440058108864733429085916392927954109944314725590758950098556991513109760871599045355054258610189920009222629391227784118536578933067532162200768112408111142115021110731900107445187734955403922470144187293970602024056652942406064101184615113779243566842311336047149767396006622923831778833173731302325162741660053390002572456069410383734906953419854919650114722834689335022576764661864630532595250136417800041415827379233503655173380741283758557001102498493237113089198106283487003030225058520047964863929279622015825870972146222540614667928697270131499340362072956956518213266361286372027834000838185920579641835952404678850816456467012890793914108776148483471455515695596694573035435841962871983614397882366460940068418989292218104650923374259244879331938925143014431488635252724366437874702141802712286424754174951797598162531093933772708024046029028652425912112434874797404878317364682580259997737809632860143160557722236459697738869857870982308547756781808568834445404196611833859447257611721058384661943492980180884154939581533269700568975940675513953240040220315659784214936947443784598154082110443748171557676558299300252057475022409541083454882202785077569281268346332901357829843950754331120530978456454396022570647840977328115888711408099894489014427119253061839770890965114853246067272044090282103668762164047374624856119676063310166566519499552342907590495696658359542582469176737197423550084705962160477441546453931948920780829433665262356431973422034925001341330921812806939990688094288773216182971976433480031438271163051341645350474631300965486818841553843112688792803367397276204832936049162335586140151875524537720425345701193713093955432559579831822084761702059241698184717469616732582600658006352069963017377661059372648121969448644394344799369193952197519795756182552461838014896498816263546256621347748100920475049252091842372001283217811864786225692344297842649982716736752004086642881662614773154743879410328420184057019873899911520017723788801=
 000002678145490787694710138406683675886762424440548647327525594133873038347266950777818028529804877891353347244255046176220880989519574806598935727647635506939520211209794328712328126947740602255036264392628020291100698432900022333877728824270241063030019536831205264726059774673235680796770108334187808344470141093691232926021244583649747591446066921535333854157441330339217364515328375889937313870826987520723914810358707312468857074455945610038118763873992681688857200178452843740327143990247797893489008808544535536081089994800692174759199578596435124153437689121057209523619989593900355037400039597165241729693472001589594642879166693443994939359639600558001937547209387175085119128575833396037478944824322315197771750730768383267287661855880237549141571520374996029107650341071074081501632143441365461865431362023790463469688071768208320226561675630348708531708110373889241713511809029065048200924851629507265095151843687852114948736130517024578482059771284515915597919026074110811882700307150650858080695566672584075215926450360584738705106755945308199980660478183563586945902705730231409948938478910176292179410952310592864745025373902249844607078729230098512959498522851990040833671698873183076996740726479481352429756295966452788332789259316653805673821716832204368483794501474641036177256005810416507649770210480747056764697918800240201155395628561684853684747063434500664449114760179367086926249813006056735202795763742271472136500817313178050955623517148960973128433455798444839070215800699075256371341531892841721456473301085595261371522078416420399702683504171019191363372883472415693921509069484448792009627325245658854979159002549542769741504596589556474585723101403486046952706847309188488390899096649210853675228464611999630360164703837131620319658277117300208326944026347808645954842782309633205645471959842390075986572806483755223497552549948718545978420793425036666212191832327909389117021539426917904222971515424022606157676379417252939026404363841301595348953340657745965591468370831371449860774296757556463049237248472613472436666799615694672489600751763956185893123579218797539971253828850163437053164723845196089466298000486042246621634263064752906475198879616484926366053597071510886820878425907736453843197228282179943365206039514850477377542684361730162273246709577442085159313947668552462343596819299335060863266863059421286080919061657175757802930378698062290163092494909661982639303946271889619023417245433500782685534406291391527022657608608130680134939380126048353657648559735671562230714451258764762350451448379438849319710473631625533527602085050858633346936315115309333355986556546113134787213610042970405680162084678021281774169131725296977361816657904233850711837826724976507876061043779177845550646612327663283839673950405472039432309339110648301347672597370034346896334064135099613033528785924976781865447506814375627647103020761819104412269362847848884053177378762432543285984193091289854949394023586451139393716370633759317698908834326333339634557238526607966375935960004339535161203546369910853171524516945554862019134684985868547068709986010719120259421723270478586992153989283736650948010894951434857207445141886625290777550599700738909777829412358941157674866550887608199469723859806486384262574182811908513849905040209776132986875560077482527819093584150609347560543627976011009349905362597935257895287412087233810106693141683912683308201407373637490835862452911394718399632093441745957478079754723679119343225931665785380948807114301164623717144211285944154289093317610519159281033583963015810556464180819928345256832572962092994993950655913067768151113345566231088759030148164710287289335782462899525700500822021472132532771242198844498579102733028256523810973405350508253183399668290339844052874956694050028526577775764032598023622192221226501334606994447870277619118208162133562541678250491647671042612088902952091163094215645902682086024337098910110924115381788866213335441814530141911754446270296630426675020592640816713810936850961517475097707179713115856513919631998747192606018612535436009162735908155778165736923393260822217415131632296810207091918499370220533980666393617256227781299273913099896641458499949922475383775878771011361417556799406151773618626138749998464514570482965286184387350245762317271666329142667987131139265167425606863654107927682419958167046956962340419295394058625063862272314570914511355913547470055072878835349142049813368019960713974852351833144227544851625677753419141348585495260230041111323576432417502998832485027071744397105338790364666312325483218209150368759120749671419554589928540715813531144241705501211397506662448276056294585639532800634727428900861538486753011006379264618338782036690340859441153926551954112364946638768223012718907190897165613382555036872673785444132692292217184974818914501886689736449912131900762592363447945036085692999163815947845753538999001633767986447907729462453017601用时0.15625秒,有4893位(前面多了5位前导0)
2021-04-12 20:53
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
我稍加修改,变成了可调用程序,发一下代码:(原代码是在另一个论坛的《[讨论]关于大整数运算》一文中见到的)

Public Function MbC(D1 As String, D2 As String) As String
 Dim j1&, j2&, e&, d&, e1&

    ' 按列法计算C=A*B
 m = Trim(D1): n = Trim(D2)
 X = Len(m) \ 4: Y = Len(n) \ 4
 m = String(4 * X + 4 - Len(m), "0") & m
 n = String(4 * Y + 4 - Len(n), "0") & n
 X = X + 1: Y = Y + 1
 Dim A(), B()
 ReDim A(1 To X): ReDim B(1 To Y)
 For i1 = 1 To X
 A(i1) = Mid(m, i1 * 4 - 3, 4)
 Next
 For i2 = 1 To Y
 B(i2) = Mid(n, i2 * 4 - 3, 4)
 Next
 ma = X: mb = Y
     MC = ma + mb
     ReDim c(MC)
     e1 = 0
     j1 = ma: j2 = ma
     For I = MC To 2 Step -1
         If I <= ma Then j2 = I - 1
         e = e1: e1 = 0
         For J = j1 To j2
             e = e + A(J) * B(I - J)
             If e > 2040000000 Then '减少进位次数
                e = e - 2040000000
                 e1 = e1 + 204000
             End If
         Next J

         If j1 > 1 Then j1 = j1 - 1
 base = 10000
         d = e \ base
         c(I) = e - d * base
         If Len(c(I)) < 4 Then
         c(I) = String(4 - Len(c(I)), "0") & c(I)
         Else
         c(I) = c(I)
         End If
 jc = c(I) & jc
         e1 = e1 + d
     Next I
     jc = d & jc
    MbC = jc
 End Function

[此贴子已经被作者于2021-4-14 19:03编辑过]

2021-04-12 20:57
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 288楼 ysr2857
其中的减少进位次数的程序有啥作用,能不能起作用?看不懂,是否影响速度,还是能提高速度?
2021-04-12 21:06
wds1
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:49
帖 子:393
专家分:2025
注 册:2016-3-10
收藏
得分:0 
上面的算法已经可以了,用的是4位数乘法。
1、速度方面,我稍微改了一下,0.046s完成乘法,改进如下:
   将以下语句修改后,,速度提高了1倍以上  
   A(i1) = Mid(m, i1 * 4 - 3, 4)
   B(i2) = Mid(n, i2 * 4 - 3, 4)
   改为:
   A(i1) = val(Mid(m, i1 * 4 - 3, 4))
   B(i2) = val(Mid(n, i2 * 4 - 3, 4))
2、多0是由于凑4位补0造成
   增加补0的计数:b0 = 4 * x + 4 - Len(m),在这个语句前   m = String(4 * X + 4 - Len(m), "0") & m
   在最后去掉补的前缀0:MbC = Mid(jc, b0, Len(jc) - b0 + 1)
2021-04-12 22:59
快速回复:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019791 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved