作者Raisto (刘大侠)
看板Prob_Solve
标题[问题] 大数相乘问题
时间Fri Jan 7 23:25:11 2011
假设有两组数要相乘
2 3 4 5 6
3 4 1 2 4
而又假设一次只能算4 X 4，所以我将其切成
2 | 3 4 5 6
3 | 4 1 2 4
先行计算3456 X 4124，最後再将其整合计算
所以假设
W = 34
X = 56
Y = 41
Z = 24
那麽
P = WY = 34 X 41
=1394
Q = XZ = 56 X 24
= 1344
R = (W+X)(Y+Z)
= (34+56)(41+24)
= (90)(65)
= 5850
进行运算
P X 10^4 + (R-P-Q) X 10^2 + Q
= 1394 X 10^4 + (5850-1394-1344) X 10^2 +1344
= 13940000+311200+1344
= 14252544
得到了14252544後，我要如何再传回去跟还未计算的数字做Merge?
最终答案应该是800412544，目前小弟不太懂的就是
我要如何把目前的结果(14252544)，变成最终答案?
有请各位大大解惑，小弟感恩
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.169.77.33
1F：→ tkcn:都说可以4x4了，为什麽还要拆开呢@@? 而既然都会拆开算了， 01/07 23:50
2F：→ tkcn:剩下来的也一样就行啦。(然後我不懂为啥要出现 R) 01/07 23:51
3F：→ Raisto:回t大: 因为原组数是5 X 5，超过程式可计算范围 01/08 00:00
4F：→ Raisto:所以依照divid and conquer想法，将其拆成可算的门槛 01/08 00:00
5F：→ Raisto:然後出现R，是因为该演算法中，有此项计算因子 01/08 00:01
6F：→ tkcn:我是说连 4x4 的部份你也拆开变成 2x2 ? 01/08 00:02
7F：→ tkcn:怎麽会到了 5x5 又不会拆了? 我想你会不会误会题意把 PQR 01/08 00:04
8F：→ tkcn:用错地方了? 01/08 00:04
9F：→ Raisto:回t大....分成wxyz并不是拆成2x2，而这样正是4x4的演算格式 01/08 09:00
10F：→ Raisto:因为书上，正是这样说的且有举范例 01/08 09:01
11F：推 suhorng:用大数加法加回去. (a*10^i)(b*10^j)=(ab)*10^(i+j) 01/08 09:40
12F：→ tkcn:能看懂4x4怎麽拆2x2，要拆5x5(当成8x8)并不是什麽难事 01/08 11:53
13F：→ Raisto:上面有说到，假设只能算4X4。所以不能算5X5 01/08 13:16
14F：→ Raisto:分割的技巧我会，目前比较不太了解如何做Merge 01/08 13:16
15F：→ Raisto:Divide and Conquer的精神就在於此，而并非把所有数列分割 01/08 13:17
16F：→ Raisto:而是要分割到门槛，计算後再逐一合并 01/08 13:17
17F：→ Raisto:我目前不太了解就是合并，而不在於5x5或8x8的分割计算 01/08 13:21
18F：推 suhorng:用大数加法加起来啊 01/08 13:22
19F：→ suhorng:4x4的拆到2x2的,所以8x8的拆到4x4的啊 01/08 13:23
20F：→ Raisto:恩 我现在有用了，只是单纯回覆t大的回文 01/08 13:23
21F：→ suhorng:啊弄完不是再加起来就好了 01/08 13:23
22F：→ Raisto:非常感谢suhorng跟tkcn的指导，小弟现在会了 01/09 00:16
23F：→ suhorng:除非是作业...私心觉得 自己想,直接模拟直式乘法就好... 01/09 10:38
24F：→ Raisto:给s大 我在写大数演算法程式，那天脑袋很浑沌 01/09 20:51
25F：→ Raisto:突然有个地方误解错误 01/09 20:51
26F：→ Raisto:一直想不出来，目前是写完了，但我用的也不是您上次提供 01/09 20:52
27F：→ Raisto:给小弟的方法，不过你的建议有点醒我一个观念 01/09 20:52
28F：→ Raisto:我整理，如果可以的话，等等po上来Y 01/09 20:52
29F：→ Raisto:然後回T大: 您给小弟的建议也正确，但我那天真的有点迟钝了 01/09 20:54