[原创]大整数的乘法

ysr

两位老师好,下面推出正规版验证方法,(上面的是忽悠人的,不要受误导):
a = 5192 02532 99870 41388 59072 78116 03754
b = 20 28240 96036 51670 42394 72512 86016
a/b = 255.98661 26089 99999 99999 99999 99999 95804 36565 16689 74965 35606 91114 52677 61131  80517  31359  44642  12656  02111  81640……
上面这个是本人编程做的“大数相除”，小数有 100 位。不知楼主能不能验证上面的计算是否正确？
对高位的验证,
20 28240 96036 51670 *255 98661 26089(商的前13位有效数字) =51920 25329 98501 30391 05541 8630,共有17位与13位相乘,得数29位,29-17=12位,
与前19位被除数前19位的比较,
51920 25329 98501 3039-5192 02532 99870 41388 =-2028349,仅末尾7位不同,有前12位相同,
对末尾数字的验证,
72512 86016(除数末尾10位)*44642  12656  (商倒数第20位后取10位)=32371 28280 49030 18496(共20位数字),
末尾10位49030 18496与余数的比较,
"余数"=72512 86016*02111  81640(商最后10位)=15313 38472 96794 6240(共19位),
49030 18496-15313 3847(余数前9位)=47498 84649(这应该是前段商值的余数,无法对照),
42394 72512 86016(除数末尾15位)*99999 99999 (商值. 后第11位后取10位)=42394 72512 43621 27487 13984,与被除数末尾比较,
8 59072 78116 0375(被除数第18位后取15位)-42394 72512 43621 (取前15位)=43512 55299 16754(共15位,无法与后面的对照),与后面余数对照,
"余数"=42394 72512 86016*99999 99999 95804 (商值. 后第21位后取15位)=42694 72512 84237 11733 36038 76864(共30位)
43512 55299 16754-42694 72512 84237 (余数前15位)=817 82786 32517(共13位),
计算器试除a/b=5192 02532 99870 41388 59072 78116 037/20 28240 96036 51670 42394 72512 86016=2.55986612609(被除数去掉2位),有效数字全部相同,
所以,老师的结果准确,相当好,程序应该推广!
和我运行的结果是一样的。
那么如果
a="204181972518847178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554"
b="20418197251884732432432432423432423324178731511459272205792.3725762648106369158720449714556708974141349142364448644923186554234"
a/b="0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525"这是保留到小数点后532位，请天山草，上面计算结果正确吗，如果正确你你计算这个花费的时间是多少?能否分享下 除法的算法。
a = 2041819725188471787315114592722057923725762648106369158720449714556708974141349142364448644923186554000
b = 204181972518847324324324324234324233241787315114592722057923725762648106369158720449714556708974141349142364448644923186554234
a/b = 0.0000000000000000000000099999999999999928694580099855311814333832059747528320512312544690041006331089896841048206045437850801125169285958648464645305455307601131698230358121859872037958276564685922576439715475993323752258151677056392535649988592943440545144186666367461644699154962489320534313136073254528566396208622912747914654284517442501275421539574253845056890372220516907916763212486881712630980329339566414076320736640270772070459866870258348245991001397346540490420567741574430516003161171367625886090379321596535525
上述结果跟 shikang999 算的完全一样。时间很短，一瞬间吧，没法测量。我用的是 VB 程序，不知道如何测量运算时间。

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

被除数与除数各取25位试除,72860 25439 24414 75520 44768 /17399 67521 24940 94886 22857 =4.18744 91048 04156 86574 26237 72097 7,无法对照,可能是a*b运算,
a*b(同样取25位)=1.26774 47623 28177 94087 84563 35294 3e+49与上面不同,
速度够快,不知是啥算法?
我才发现,计算机程序附件中的计算器,是可以算33位有效数字的,且数字精确可靠,网上的在线计算器,能算20多位的,当数字超过20位结果末尾就不可靠,甚至有多位不对,真是!!!
  两位老师的程序非同1般,应该推广,但当今科学界简直是"无政府状态",好的东西无法推广,没有人给与客观公正的评价,伪劣产品却大行其道,乱收"买路钱",这样下去,后果不堪!
若好的新的东西能不断推广和发展,何必花巨资下载老外的那个"神马牛逼"的东东呢?
  



  


  

ysr

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

编程序累人呀!只会VB简单的+-*/啊,大数不会!什么是数组,如何做?分段计算如何循环?^^6^66^^^^^^^^^^^^^^,尼玛,晕了!
希望帮助,做可调用程序!!!要组成快速分解因数和RSA密码的破解程序,难!!!
以下为移花接木的大数乘法VB代码及1个实际例子的答案:
Private Sub Command1_Click()
D1 = Text1.Text
D2 = Text2.Text
Text3.Text= MPC(Text1.Text, Text2.Text)
End Sub
Public Function MPC(D1 As String, D2 As String) As String
Dim X, Y ';两数长度
X = Len(D1): Y = Len(D2)
Dim A() As Integer
ReDim A(1 To X + Y, 1 To Y)
Dim I, J, C1, C2, CJ, JW
If Check1.Value = 1 Then
For C = 1 To X + Y
   MPC = MPC & "-"
Next
MPC = MPC & vbCrLf
End If
For J = Y To 1 Step -1 ';D2
JW = 0 ';进位清0
C2 = Mid$(D2, J, 1) ';每位数
For I = X To 1 Step -1 ';D1
   C1 = Mid$(D1, I, 1) ';每位数
   CJ = C1 * C2 + JW ';计算乘积
   C = I + J: R = Y + 1 - J
   A(C, R) = CJ Mod 10 ';本位
   JW = CJ \ 10 ';进位
Next
A(C - 1, R) = JW
If Check1.Value = 1 Then
   Dim T, M
   T = ""
   For C = 1 To X + Y
    MPC = MPC & A(C, R)
   Next
   MPC = MPC & vbCrLf
End If
Next
Dim B() As Integer
ReDim B(1 To X + Y)
JW = 0
For I = X + Y To 1 Step -1
Bit = JW
For J = 1 To Y
   Bit = Bit + A(I, J)
Next
B(I) = Bit Mod 10
JW = Bit \ 10
Next
If Check1.Value = 1 Then
For C = 1 To X + Y
   MPC = MPC & "-"
Next
MPC = MPC & vbCrLf
End If
If B(1) > 0 Then
MPC = MPC & B(1)
Else
MPC = MPC & Space(1)
End If
For I = 2 To X + Y
MPC = MPC & B(I)
Next
End Function
被乘数123456789123456789123456789,
乘数123456789,
积------------------------------------
000000001111111102111111102111111101
000000009876543129876543129876543120
000000086419752386419752386419752300
000000740740734740740734740740734000
000006172839456172839456172839450000
000049382715649382715649382715600000
000370370367370370367370370367000000
002469135782469135782469135780000000
012345678912345678912345678900000000
------------------------------------
15241578765432099765432099750190521

ysr

以上代码注意1点,要使复选框Check1.的Value 属性为1.我费好大劲才查到Check1.为复选框控件.

ysr

以上代码缺点是除了显示乘积外,还有如下中间数据:
------------------------------------
000000001111111102111111102111111101
000000009876543129876543129876543120
000000086419752386419752386419752300
000000740740734740740734740740734000
000006172839456172839456172839450000
000049382715649382715649382715600000
000370370367370370367370370367000000
002469135782469135782469135780000000
012345678912345678912345678900000000
------------------------------------
  敬请高手指点,修改1下,使仅显示乘积,以便调用此结果,非常感谢!!

ysr

天山草老师59楼的大数除法程序还是好使的,能在程序中调用么?如何调用?

ysr

以下为该程序的1个结果:
15241578765432099765432099750190521/123456789=123456789123456789123456789,

ysr

62楼的乘法是1位1位相乘,1位1行,中间数据太多,大数看不到结果,中间数据就占满了,要改成分段算就好了,可能速度还会提高1点,且把中间数据不要显示,喜欢 yeduhengzhou 和zhaolu48老师的,可惜看不懂他的代码!
59楼天山草老师的除法的结果,小数点后的位数太多,不过改1下就好了,看明白1点,是把Z=532-9改1下吗?我需要整数部分,小数部分只保留8位就行!
  欢迎高手指点!谢谢各位老师长期的鼓励支持和帮助!

ysr

62楼的为啥非加个复选框呢?Check1.value = 1,还有如何就让中间数据不显示?

ysr

自己顶1下,求高手帮助!

ysr

62楼修改了1下为:
Private Sub Command1_Click()
D1 = Text1.Text
D2 = Text2.Text
Text3.Text = MPC(Text1.Text, Text2.Text)
End Sub
Public Function MPC(D1 As String, D2 As String) As String
Dim X, Y ';两数长度
X = Len(D1): Y = Len(D2)
Dim A() As Integer
ReDim A(1 To X + Y, 1 To Y)
Dim I, J, C1, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 0 ';进位清0
C2 = Mid$(D2, J, 1) ';每位数
For I = X To 1 Step -1 ';D1
  C1 = Mid$(D1, I, 1) ';每位数
  CJ = C1 * C2 + JW ';计算乘积
  C = I + J: R = Y + 1 - J
  A(C, R) = CJ Mod 10 ';本位
  JW = CJ \ 10 ';进位
Next
A(C - 1, R) = JW
Next
Dim B() As Integer
ReDim B(1 To X + Y)
JW = 0
For I = X + Y To 1 Step -1
Bit = JW
For J = 1 To Y
  Bit = Bit + A(I, J)
Next
B(I) = Bit Mod 10
JW = Bit \ 10
Next
If B(1) > 0 Then
MPC = MPC & B(1)
Else
MPC = MPC
End If
For I = 2 To X + Y
MPC = MPC & B(I)
Next
End Function
Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub
运算结果:
因数123456789123456,
因数123456789,
积15241578765432002342784,
这样好些,只是不如分段算更快些!