[問題] 大數相乘問題

[Raisto (劉大俠)]

假設有兩組數要相乘

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
→ tkcn:都說可以4x4了，為什麼還要拆開呢@@?  而既然都會拆開算了，
→ tkcn:剩下來的也一樣就行啦。(然後我不懂為啥要出現 R)
→ Raisto:回t大: 因為原組數是5 X 5，超過程式可計算範圍
→ Raisto:所以依照divid and conquer想法，將其拆成可算的門檻
→ Raisto:然後出現R，是因為該演算法中，有此項計算因子
→ tkcn:我是說連 4x4 的部份你也拆開變成 2x2 ?
→ tkcn:怎麼會到了 5x5 又不會拆了?  我想你會不會誤會題意把 PQR
→ tkcn:用錯地方了?
→ Raisto:回t大....分成wxyz並不是拆成2x2，而這樣正是4x4的演算格式
→ Raisto:因為書上，正是這樣說的且有舉範例
推 suhorng:用大數加法加回去. (a*10^i)(b*10^j)=(ab)*10^(i+j)
→ tkcn:能看懂4x4怎麼拆2x2，要拆5x5(當成8x8)並不是什麼難事
→ Raisto:上面有說到，假設只能算4X4。所以不能算5X5
→ Raisto:分割的技巧我會，目前比較不太了解如何做Merge
→ Raisto:Divide and Conquer的精神就在於此，而並非把所有數列分割
→ Raisto:而是要分割到門檻，計算後再逐一合併
→ Raisto:我目前不太了解就是合併，而不在於5x5或8x8的分割計算
推 suhorng:用大數加法加起來啊
→ suhorng:4x4的拆到2x2的,所以8x8的拆到4x4的啊
→ Raisto:恩 我現在有用了，只是單純回覆t大的回文
→ suhorng:啊弄完不是再加起來就好了
→ Raisto:非常感謝suhorng跟tkcn的指導，小弟現在會了
→ suhorng:除非是作業...私心覺得 自己想,直接模擬直式乘法就好...
→ Raisto:給s大 我在寫大數演算法程式，那天腦袋很渾沌
→ Raisto:突然有個地方誤解錯誤
→ Raisto:一直想不出來，目前是寫完了，但我用的也不是您上次提供
→ Raisto:給小弟的方法，不過你的建議有點醒我一個觀念
→ Raisto:我整理，如果可以的話，等等po上來Y
→ Raisto:然後回T大: 您給小弟的建議也正確，但我那天真的有點遲鈍了