作者EdisonX (閉上眼的魚)
站內Prob_Solve
標題[問題] 請教這份大數乘法複雜度
時間Wed Jan 2 10:33:51 2013
在不碰 fft , 搞效能時想到的一招,
但不確定 Big-O 為何, 也不確定這種方式會比較快
(與 Cij = ΣΣAi*Bj 比)
想請教各位先進。
---
假設以 100 為進位，計算 1234 * 5678
1234 * 5678
= (12*100 + 34) * (56 * 100 + 78)
= { 12*56*10000 + (12*78+34*56)*100 + 34*78 }
[00][00][12][34]
x [00][00][56][78]
-----------------------
(0) rst = [00][00][00][00]
(1) 34*78 = 2652
rst = [00][00][00][2652]
= [00][00][26][52]
(2) 12*78+34*56 = 2840
rst = [00][00][26+2840][52]
= [00][00][2866][52]
= [00][28][66][52]
(3) 12*56 = 672
rst = [00][28+672][66][52]
= [00][700][66][52]
= [07][00][66][52]
整個流程可以再用遞回不斷分割，分割過程是 O(logn)，
但最後的相乘還要是 O(n^2)，請教整體的 Big-O 為何？
謝謝各位先進不吝賜教，感激不盡。
--
~ 這輩子與神手無緣
我只好當神獸了 ~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
1F：推 FRAXIS:你分解成4個小問題 每個小問題都是原本的一半 所以是O(n^2) 01/02 10:42
2F：→ FRAXIS:你可以參考一下 Karatsuba algorithm 01/02 10:43
3F：→ EdisonX:原來如此,看來我的想法似乎沒助益,謝謝 F 大 :) 01/02 10:57
4F：→ EdisonX:疑！我查一下 Karatsuba algorithm, 真的有助益, 感謝 :) 01/02 11:00