[原创]大整数的乘法
下面引用由ysr在 2012/03/07 03:21pm 发表的内容:算法和数学原理我搞出来了,除法的文章已投稿,在处理,不会编程,没有法验证!
a = 5192025329987041388590727811603754
b = 20282409603651670423947251286016
a/b = 255.9866126089999999999999999999999580436565166897496535606911145267761131805173135944642126560211181640……
上面这个是本人编程做的“大数相除”,小数有 100 位。不知楼主能不能验证上面的计算是否正确?
[原创]大整数的乘法
和我运行的结果是一样的。那么如果
a="204181972518847178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554"
b="20418197251884732432432432423432423324178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554234"
a/b="0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525"这是保留到小数点后532位,请天山草,上面计算结果正确吗,如果正确你你计算这个花费的时间是多少?能否分享下 除法的算法。
[原创]大整数的乘法
[这个贴子最后由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(与除数末尾比较,还不对,无法判断?)
[原创]大整数的乘法
那个乘法的验证64545644*13222465=853452518692460,,
555 555*222 222=123 456 543 210,,
[原创]大整数的乘法
a = 5192 02532 99870 41388 59072 78116 03754b = 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在 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,不是偶然的,说明数据是准确的,
©数学中国 -- 数学中国 www.mathchina.com Kj <
与余数比较,余数=31865 54234*0.99999 28694(商的次高位的数字)=31865 31511.95637 90396,Y&
©数学中国 -- 数学中国 www.mathchina.com N
631865 31511与3186554233.6813445766整数部分位数相同,最高位相同,,V
所以,结论正确!PK
两位老师的结论是 相当 的准确的!
[原创]大整数的乘法
a = 2041819725188471787315114592722057923725762648106369158720449714556708974141349142364448644923186554000b = 204181972518847324324324324234324233241787315114592722057923725762648106369158720449714556708974141349142364448644923186554234
a/b = 0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525
上述结果跟 shikang999 算的完全一样。时间很短,一瞬间吧,没法测量。我用的是 VB 程序,不知道如何测量运算时间。
[原创]大整数的乘法
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 #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 #1,
Print "aa1 = "; aa1: Print #1, "aa1 = "; aa1
Print "bb1 = "; bb1: Print #1, "bb1 = "; bb1
Print "ppp = ";: Print #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$(aa1)) < Len(Trim$(bb1)) Then ';被除数小于除数时
ppp = ppp + "0"
aa1 = aa1 + "0"
Z = Z - 1
GoTo 1
Else
GoSub sub3
If Val(sy$) * Val(aa1) = 0 Then GoTo 4';余数或被除数为零停止计算
GoTo 3
End If
End If
2:
GoSub sub3
If Val(sy$) * Val(aa1) = 0 Then GoTo 4 ';余数或被除数为零停止计算
ppp = ppp + "." ';以下计算小数部分
3: For iv = 1 To Z '; Z 是事先设定的小数位数
If Val(sy$) * Val(aa1) = 0 Then GoTo 4 ';余数或被除数为零停止计算
aa1 = sy$ + "0"
GoSub sub3
Next iv
4:Print ppp: Print #1, ppp
Return
sub3: ';大数相除
ccc = 0
vvv = 0';试余数不大于除数时的标志
If (Len(aa1) = Len(bb1) And aa1 = bb1) Then pp = "1": sy$ = "0": GoTo 50
If (Len(aa1) = Len(bb1) And aa1 < bb1) Or Len(Trim$(aa1)) < Len(Trim$(bb1)) Then ';被除数小于除数时
pp = "0"
sy$ = 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$ = ""
For i = fb To 1 Step -1 ';……………… 求试商的精确积
qq$ = qq$ & 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$ = "" ';以下做出试余数的字符串 ssy$
For i = fb To 1 Step -1
ssy$ = ssy$ & ayy(i)
11: Next i
If (Len(ssy$) = Len(bb1) And ssy$ > bb1) Or Len(Trim$(ssy$)) > Len(Trim$(bb1)) Then
vvv = 1 ';试余数大于除数时的标志
For i = 1 To fb ';试余数减去除数,得到正确余数 sy$
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$ = "" ';把 ay(i) 组装成 sy$
For i = 1 To fb
sy$ = Trim$(Str$(ay(i))) & sy$
Next i
71: If Mid$(sy$, 1, 1) = " " Or Mid$(sy$, 1, 1) = "0" Then sy$ = Mid$(sy$, 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$ = "" ';以下做出余数的字符串 sy$
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$ = sy$ & 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$ = sy$ & ay(i)
30: Next
End If
If Mid(sy$, 1, 1) = "-" Then ccc = -1: GoTo 10 ';余数为负,重做余数
40: If Mid(sy$, 1, 1) = "0" Then sy$ = Mid(sy$, 2) ';去掉余数前面的多余零
If Mid(sy$, 1, 1) = "0" Then GoTo 40
50: If sy$ = "" Then sy$ = "0"
If mv = 1 And sy$ <> "0" Then sy$ = Mid(sy$, 1, Len(sy$) - 2)
If mv = 1 And sy$ = "0" Then sy$ = "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-=-=-=-=- 以下内容由 天山草 在 时添加 -=-=-=-=-
看来,用业余方法研究这些问题,很难有什么大的成果。