[原创]大整数的乘法

天山草

下面引用由ysr在 2012/03/07 03:21pm 发表的内容：
算法和数学原理我搞出来了,除法的文章已投稿,在处理,不会编程,没有法验证!

a = 5192025329987041388590727811603754
b = 20282409603651670423947251286016
a/b = 255.9866126089999999999999999999999580436565166897496535606911145267761131805173135944642126560211181640……
上面这个是本人编程做的“大数相除”，小数有 100 位。不知楼主能不能验证上面的计算是否正确？

shikang999

和我运行的结果是一样的。
那么如果
a="204181972518847178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554"
b="20418197251884732432432432423432423324178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554234"
a/b="0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525"这是保留到小数点后532位，请天山草，上面计算结果正确吗，如果正确你你计算这个花费的时间是多少?能否分享下 除法的算法。

ysr

[这个贴子最后由ysr在 2012/03/08 01:56pm 第 3 次编辑]

255 *202824=51720120,除数和被除数取3和6位,积8位,8-6=2,8-3=5,从大到小有2位相同,如果有少与2位或没有相同也可能正常.
255*286016=72934080,余数为0.9866126*286016=282186
72934080+282186=73216266,
末尾从小到大有0位相同,除末尾1位外,是否有问题?
末尾数不对则可能就错了,不知对否?
可能我计算错了重新,
255.9866126089999999999999999999999580436565166897496535606911145267761131805173135944642126560211181640*251286016=64325856031.851
可能还错要255*286016=72934080加被除数末尾8位
51286016+72934080=124220096
727811603754(被除数末尾)-64325856031=663 485 747 723(与除数末尾比较,还不对,无法判断?)

ysr

那个乘法的验证
64545644*13222465=853452518692460,,
555 555*222 222=123 456 543 210,,

ysr

a = 5192 02532 99870 41388 59072 78116 03754
b = 20 28240 96036 51670 42394 72512 86016
a/b = 255.9866126089999999999999999999999580436565166897496535606911145267761131805173135944642126560211181640……
上面这个是本人编程做的“大数相除”，小数有 100 位。不知楼主能不能验证上面的计算是否正确？
对老师的结论再次验证如下,
高位数字的验证:
5192 02532 99870 /20 28240 96036 =255.98661260965
5192 02532 99870/255=203608836470.078,
20 28240 96036 *255=51720144489180,
均有2位相同,
末尾数字:
72512 86016*255=184 907 793 4080,取末尾7位,与被除数末尾比较,
78116 03754- 793 4080=780 366 9674,再与余数比较,
余数=72512 86016*0.98661260899999999999999999999995804=715 421 0214.85098,
整数部分位数相同,最高位相同,
所以,老师的结果是对的!

ysr

[这个贴子最后由ysr在 2012/03/09 11:13pm 第 1 次编辑]


上面对两位老师的验证有问题，重新做，如下：
a = 5192 02532 99870 41388 59072 78116 03754^,
b = 20 28240 96036 51670 42394 72512 860162/4u^:
a/b = 255.9866126089999999999999999999999580436565166897496535606911145267761131805173135944642126560211181640……J
上面这个是本人编程做的“大数相除”，小数有 100 位。不知楼主能不能验证上面的计算是否正确？o
©数学中国 -- 数学中国 www.mathchina.com　　`FQ
对老师的结论再次验证如下,B&=8a.
高位数字的验证:dY
5192 02532 99870 /20 28240 96036 =255.98661260965J!Xy?
5192 02532 99870/255=203608836470.078,Q{J
20 28240 96036 *255=51720144489180,L2MU8
均有2位相同,cPJo
末尾数字:f
72512 86016*255=184 907 793 4080,取末尾7位,与被除数末尾比较,@?xx
78116 03754- 793 4080=780 366 9674,再与余数比较,=CqH
余数=72512 86016*0.9866126=7154210149.5894016,}
整数部分位数相同,最高位相同,运算结果是对的，但精确度无法验证，用如下法验证，6算运算运算>(L
5192 02532 99870 41388 59072 78116 03754,（被除数）
b = 20 28240 96036 51670 42394 72512 86016=2^104（除数）
1/20 28240 96036 51670 42394 72512 86016=4.93038 06576 31323 78382 33035 0174e-32
255.986612608999999999999999999999958043656516689749653560691114526776113180517 31359 44642 12656 02111 81640……
我们知道1/9=0.11111……，这个很重要，以下看看9的倒数的性质，
2/9=0.2222222……
11/9=1.22222……
3/9=0.33333……
12/9=1.3333……
4/9=0.44444……
13/9=1.44444……
5/9=0.555555……
23/9=2.555555……
……
运用这个可以判断精确度，
5192 02532 99870 41388 59072 78116 03754/9=57689 17033 31893 48762 11919 79067083.777……
31359 44642 12656 02111 81640（商末尾25位）*4/9=13937 53174 27847 12049 69617.7777777777……
可见末尾数是准确的 ，

所以,老师的结果是对的!KlH
那么如果L.C[OX
a="204181972518847178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554"G\{1j
b="20418197251884732432432432423432423324178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554234"i0
a/b="0.00000 00000 00000 00000 00099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525"这是保留到小数点后532位，请天山草，上面计算结果正确吗，如果正确你你计算这个花费的时间是多少?能否分享下 除法的算法。!a
©数学中国 -- 数学中国 www.mathchina.com　　r$
对楼上朋友的结论验证如下,0
对高位验证,K$a#}9
20418 19725 *0.9999999999999992869=2041819725,:T
©数学中国 -- 数学中国 www.mathchina.com　　~[
对末尾验证,oZS=
©数学中国 -- 数学中国 www.mathchina.com　　aE6@"
31865 54234*0.99999 99999 =3186554233.6813445766,BvQjQg
©数学中国 -- 数学中国 www.mathchina.com　　!
与被除数末尾比较,4923186554-3186554233.=1736632321,lh
实际上我们去掉了23个0，位数搞不对了，观察数据，有几位相同是86554，不是偶然的，说明数据是准确的，
&copy;数学中国 -- 数学中国 www.mathchina.com　　Kj <
与余数比较,余数=31865 54234*0.99999 28694（商的次高位的数字）=31865 31511.95637 90396,Y&
&copy;数学中国 -- 数学中国 www.mathchina.com　　N
631865 31511与3186554233.6813445766整数部分位数相同,最高位相同,,V
所以,结论正确!PK
两位老师的结论是      相当   的  准确的！

  

天山草

a = 2041819725188471787315114592722057923725762648106369158720449714556708974141349142364448644923186554000
b = 204181972518847324324324324234324233241787315114592722057923725762648106369158720449714556708974141349142364448644923186554234
a/b = 0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525
上述结果跟 shikang999 算的完全一样。时间很短，一瞬间吧，没法测量。我用的是 VB 程序，不知道如何测量运算时间。

shikang999

1、我是使用的VB.NET编写的函数。我也不知道怎么测试运行时间,但是我喜欢用TickCount函数来大概估测一下,你不妨也使用这个函数试一试。
2、由于我发现我写的大数的除法运算速度还是很慢的,如下一个例子:
a=7286025439244147552044768094494970670453821245103478375113499668041140478785169550238619398440399354360511215249981485425965375223278917156823159189309716583125389316214011310664761586451135133634051116088202871228049435860420534523953539377020921360927922119685232294019303511214566996715426428121838461181533186903657201412864629321377235160683482314413148591336984203200351323014462317841013401383182724797916811965352050885789411664364124676151711501269291880401829929488523556711481149544177837066677475459160710896270712672659031843848967118434756044257531716636028001821339476153114482200285750574045687126830139714288434062087475459581768764210984229659577958821325419218720000411703661584127503689314021935132293912819290559551694336547957018392178821463618384242222108009931463934140107045125647452181323584511441517072426941579794694494129308237362501191542248726399873954218208650501821737541293117302813115633125320229241289513862204238347167255266499275311877682801284622241944430249183
b=1739967521249409488622857855152482416357727328021957794584620460158092615420722903969261762619449476903591896186034426581333290897101515173166082724019857096758736527502097897321100101198043357931706352423299562981122414178221803487287465469198943719356861866767271537218826850154557464947952156144804806231877363515222636671457150740996161922194391695911238913395895263281221315776201239486178522505110670374191375926443178420582812210228465400926515906519361544762775146176798532749228385736405714274243573246793666151279769498465071546199720130678929118501022361377624399277585934205569442918960538117843547791149732076202619264287356279011106542261791848080664665318417927161897245058150837099393617799060309630720686110191380009209199569898658131269118011154929354279281125450378127543624442091703012825421120853352041200539913155268414917549923421654787880159744584963712766814212727501359385576943729842293028704159561967014301662872261943671905496833347460056109083868619462875038800974571419
a/b=7286025439244147552044768094494970670453821245103478375113499668041140478785169550238619398440399354360511215249981485425965375223278917156823159189309716583125389316214011310664761586451135133634051116088202871228049435860420534523953539377020921360927922119685232294019303511214566996715426428121838461181533186903657201412864629321377235160683482314413148591336984203200351323014462317841013401383182724797916811965352050885789411664364124676151711501269291880401829929488523556711481149544177837065868505231173124236820855075704636366570177371509778260216391868140767498258058947673403832442172774726041082417211900923029524576950174483820882703208333421315973198425334164846487947133979876705915802422662668631260494759668772885641310801513744504372897972418710118040660303613668807848056365045423008242479944638988838692684819787881635446009120754375691038896343733918619182906337409933966410120509163144051939927163392190033650580109779966993712350408864228363394096017247255065520711670956455.765753641849466967929396076517146294535561048535796042061720245540961379681763106266820707923527075315385457058652437134280660762677704440709714075208514004040847752512719432340025297325208904392134696109430942216656332932598146699244261746223864691014870800917149898944917782946190947168759737279627848590468016649497141818527590737212605571499248788269883582499777841563278388906034867898894011393411809765725542028979815681493027871647966556852353933047132622079394602204918796425969978500889845213';小数点后500位
运行上面的除法花费31ms(当然,不同的环境应该会有所差别),而对上面a*b进行运算花费的时间基本为0ms相比,确实不能让自己容忍.希望大家能一起讨论下大数的除法的算法。
当然,我可以先说下我的大数除法的算法。由于字数我直接连接到我的博客日志http://blog.163.com/shikang999@126/blog/static/172624896201111410352184/
希望天山草也能说下你的除法的算法！

天山草

看来 shikang999 对大数运算有研究。本人的方法很普通，是将数字转换为字符串，由于字符串的长度不可以超过 255，所以好像位数太多了不行。下面是程序：

';商为整数及小数的大数相除，可调用
  Private Sub form_Click()
  Open "相除结果111.txt" For Output As &#35;1
   
    Dim a1(100000) As Long   ';……………… 被除数的各位数字
    Dim ay(100000) As Long  ';……………… 余数的各位数字（最后一次试商要修正时）
    Dim ayy(100000) As Long  ';………………余数的各位数字（最后一次试商不必修正时）
    Dim b1(100000) As Long   ';……………… 除数的各位数字
    Dim c1(100000) As Long   ';……………… 近似商与除数相乘后的各位数字
   
    Dim d(10) As Long
   
    Dim aa1 As String     ';作为被除数的输入字符串
    Dim bb1 As String     ';作为除数的输入字符串
    Dim pp As String      ';商的每一位
    Dim ppp As String     ';作为商的输出字符串
    Dim s1(1000) As Long  ';……………… 商的各位数字
    Dim js As Long        '; js 是商的位数加一
    Dim ta, tb, j, e As Long
    Dim fa As Long  ';………………………… 被除数的位数
    Dim fb As Long  ';………………………… 除数的位数
   
   
   aa1 = "2041819725188471787315114592722057923725762648106369158720449714556708974141349142364448644923186554000"
    bb1 = "204181972518847324324324324234324233241787315114592722057923725762648106369158720449714556708974141349142364448644923186554234"
           
  GoSub sub1
  
999: Close
    Exit Sub
   
sub1:
    Z = 532 - 9 ';100    ';需要计算的小数位数
   
    Print: Print &#35;1,
    Print "aa1 = "; aa1: Print &#35;1, "aa1 = "; aa1
    Print "bb1 = "; bb1: Print &#35;1, "bb1 = "; bb1
    Print "ppp = ";: Print &#35;1, "ppp = ";
   
    pp = "": ppp = "": mv = 0
    If Len(bb1) <= 2 Then aa1 = aa1 + "00": bb1 = bb1 + "00"  ';除数小于 3 位时
    mv = 0
    If Val(aa1) < Val(bb1) And Val(aa1) <> 0 Then       ';除数大于被除数时
       ppp = "0."
        Z = Z - 1
       aa1 = aa1 + "0"
       mv = 1
    End If
   
    If mv = 0 Then
       GoTo 2
       Else
1:   If (Len(aa1) = Len(bb1) And aa1 < bb1) Or Len(Trim&#36;(aa1)) < Len(Trim&#36;(bb1)) Then ';被除数小于除数时
       ppp = ppp + "0"
       aa1 = aa1 + "0"
       Z = Z - 1
       GoTo 1
       Else
       GoSub sub3
       If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4  ';余数或被除数为零停止计算
       GoTo 3
    End If
    End If
2:
    GoSub sub3
   
    If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4     ';余数或被除数为零停止计算
                                          
    ppp = ppp + "."                            ';以下计算小数部分
   
3:   For iv = 1 To Z                           '; Z 是事先设定的小数位数
    If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4     ';余数或被除数为零停止计算
    aa1 = sy&#36; + "0"
    GoSub sub3
    Next iv
4:  Print ppp: Print &#35;1, ppp
    Return
   
   
   
sub3:      ';大数相除
    ccc = 0
    vvv = 0  ';试余数不大于除数时的标志
    If (Len(aa1) = Len(bb1) And aa1 = bb1) Then pp = "1": sy&#36; = "0": GoTo 50
    If (Len(aa1) = Len(bb1) And aa1 < bb1) Or Len(Trim&#36;(aa1)) < Len(Trim&#36;(bb1)) Then ';被除数小于除数时
      pp = "0"
      sy&#36; = aa1
      GoTo 50
    End If
   
     
   mv = 0   ';如果除数位数小于 3 位，则分子分母同放大 100 倍：
   If Len(bb1) <= 2 Then aa1 = aa1 + "00": bb1 = bb1 + "00": mv = 1

   fa = Len(aa1)  ';把被除数的各位数码放在数组 a1(i)中
   For i = 1 To fa  ';a1(1)为最低位，a1(fa)为最高位
     a1(i) = Mid(aa1, fa - i + 1, 1)
   Next i
   
    fb = Len(bb1)  ';把除数的各位数码放在数组 b1(i)中
   For i = 1 To fb   ';b1(1)为最低位，b1(fb)为最高位
     b1(i) = Mid(bb1, fb - i + 1, 1)
   Next i
   
    ';以下取除数的近似数
   e = b1(fb) * 1000 + (b1(fb - 1)) * 100 + b1(fb - 2) * 10 + b1(fb - 3) + 1
   ta = fa: js = 0
   
   For j = fa - fb + 1 To 1 Step -1     ';………… 做除法求商，求余数
     js = js + 1
     f = a1(ta) * 1000 + a1(ta - 1) * 100 + a1(ta - 2) * 10 + a1(ta - 3)
   ';取被除数的近似数
     s1(js) = Int(f / e)   ';…………………………………… 试商
   For i = 1 To fb      ';…………………………………… 求试商的积
   c1(i) = b1(i) * s1(js)  ';…… 近似商与除数相乘后的各位数字
   Next i
   
   d(0) = 0
   For i = 1 To fb - 1  ';…………………………………… 满 10 进位
     d(1) = Int((c1(i) + d(0)) / 10): c1(i) = c1(i) + d(0) - d(1) * 10
     d(0) = d(1)
   Next i
   c1(fb) = c1(fb) + d(0)
   
   qq&#36; = ""
   For i = fb To 1 Step -1     ';……………… 求试商的精确积
   qq&#36; = qq&#36; & c1(i)           ';…… 试商与除数相乘后的精确积
   Next i
   
   For i = fb To 1 Step -1
      a1(ta - fb + i) = a1(ta - fb + i) - c1(i)
   Next i
   For i = 1 To fb
       If a1(ta - fb + i) < 0 Then
       a1(ta - fb + i) = a1(ta - fb + i) + 10
       a1(ta - fb + i + 1) = a1(ta - fb + i + 1) - 1
     End If
   Next i
     a1(ta - 1) = a1(ta - 1) + a1(ta) * 10
     ta = ta - 1
   Next j   ';至此，已初步算出最后的试商
   
   a1(fb - 1) = a1(fb - 1) Mod (10)
   
   For i = fb To 1 Step -1
   ayy(i) = a1(i)          ';试余数的各位数码
   Next
   
   ssy&#36; = ""    ';以下做出试余数的字符串 ssy&#36;
   For i = fb To 1 Step -1
   ssy&#36; = ssy&#36; & ayy(i)
11: Next i
   
   If (Len(ssy&#36;) = Len(bb1) And ssy&#36; > bb1) Or Len(Trim&#36;(ssy&#36;)) > Len(Trim&#36;(bb1)) Then
      vvv = 1    ';试余数大于除数时的标志
      For i = 1 To fb   ';试余数减去除数，得到正确余数 sy&#36;
      ay(i) = ayy(i) - b1(i)
       If ay(i) < 0 Then
         ay(i) = ay(i) + 10
         ayy(i + 1) = ayy(i + 1) - 1
       End If
      Next i
     sy&#36; = ""             ';把 ay(i) 组装成 sy&#36;
     For i = 1 To fb
      sy&#36; = Trim&#36;(Str&#36;(ay(i))) & sy&#36;
     Next i
71: If Mid&#36;(sy&#36;, 1, 1) = " " Or Mid&#36;(sy&#36;, 1, 1) = "0" Then sy&#36; = Mid&#36;(sy&#36;, 2) Else GoTo 72
   GoTo 71   ';去掉结果中的多余 0
   End If
72:
   For i = 1 To fb - 1
     c1(1) = a1(i) - b1(i)
     ay(i) = c1(1)   ';最后一次试商要修正时，这就是余数各位数（除最高位）
   If c1(1) < 0 Then
     ccc = -1
     c1(1) = c1(1) + 10: a1(i + 1) = a1(i + 1) - 1
   End If
   Next i
   c1(1) = a1(fb) - b1(fb)
   
   ay(fb) = c1(1)  ';最后一次试商要修正时，这就是余数的最高位
   
   If c1(1) >= 0 Then         '; c(1) 不是负数时最后一次试商要修正
      s1(js) = s1(js) + 1     '; 所谓修正就是加一
   End If
   
   For i = js To 1 Step -1
   If s1(i) >= 10 Then   ';由于修正，商的某一位有大于10者，要调整进位
     s1(i) = s1(i) - 10: s1(i - 1) = s1(i - 1) + 1
   End If
   Next i

   If js = 1 Then       ';以下做出商的字符串 pp
     pp = s1(js)
   End If
   If js >= 2 Then
     pp = 10 * s1(1) + s1(2)
   End If
   For i = 3 To js
   pp = pp & s1(i)
   Next i
      
   If vvv = 1 Then GoTo 50  ';试余数大于除数
   
10: sy&#36; = ""    ';以下做出余数的字符串 sy&#36;
   If ccc = -1 Then    ';最后一次试商不必修正时的余数
   For i = fb To 1 Step -1
   If ayy(i) <> 0 Then yyy = 1
   If ayy(i) = 0 And yyy = 0 Then GoTo 20
   sy&#36; = sy&#36; & ayy(i)
20: Next i
   End If
   
   If ccc = 0 Then    ';最后一次试商须修正时的余数
   For i = fb To 1 Step -1
   If ay(i) <> 0 Then yyy = 1
   If ay(i) = 0 And yyy = 0 Then GoTo 30
   sy&#36; = sy&#36; & ay(i)
30: Next
   End If
   If Mid(sy&#36;, 1, 1) = "-" Then ccc = -1: GoTo 10   ';余数为负，重做余数
40: If Mid(sy&#36;, 1, 1) = "0" Then sy&#36; = Mid(sy&#36;, 2)   ';去掉余数前面的多余零
   If Mid(sy&#36;, 1, 1) = "0" Then GoTo 40
   
50: If sy&#36; = "" Then sy&#36; = "0"
   If mv = 1 And sy&#36; <> "0" Then sy&#36; = Mid(sy&#36;, 1, Len(sy&#36;) - 2)
   If mv = 1 And sy&#36; = "0" Then sy&#36; = "0"
   ppp = ppp + pp     ';包括整数及小数的商
   
90: Return
   
   End Sub
   

天山草

[这个贴子最后由天山草在 2012/03/10 00:56pm 第 1 次编辑]

另外，第 58 楼那个相除的结果没有写出来，应该是：（小数后 1000 位）
这是用 mathematica 算的。花费时间是 1.37694*10^-17 秒,若是计算到小数后面一百万位，用时是 0.031 秒。能算得这样快，真是不可思议。
以下是小数后 1000 位的值：
4.18744910480415686574262176837490458942323515788162026451816193403389\
1092558488368702257615611368641000628561366805354134126939859290544819\
8180638692503945093807701140149302524898001319560448754138586540155310\
5616314214473176531068312205407824089573100259688017230177355352966427\
5598322091973008766111438979877583976483143842630152284428311818951247\
9633863363579215260129514654432243118905994397600069598018225040974326\
4881392984588976454929827665311359136256963767160437109542599021231315\
0440450225127464934096819631200529025907345826664201390471778625501790\
4757379923336273621704866180951584540283435190214408871964559705324740\
0425019041349376969441838851168062119342124330700975404865199616919960\
6775215305377599510875891559201021401421795380148873036227394164320180\
9319128199045966347447631972052731621675360156926788725201083295776002\
8985919161059810256589802340562827237553492806147653765893180341848310\
5048384703798188693291525692120840379479256163535732814248460999938057\
021748250276259988186[br][br]-=-=-=-=- 以下内容由 天山草 在 时添加 -=-=-=-=-
看来，用业余方法研究这些问题，很难有什么大的成果。