作者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