作者j12345453 (CJentalL)
看板Grad-ProbAsk
標題演算法 Divide and conquer
時間Sat Dec 11 13:20:03 2021
https://i.imgur.com/cAHPDBO.jpg
如題
清大這題把Bit切分成前後半
又特別講解要做出u1v2+u2v1
原因是什麼呀
這樣跟u1v1直接乘有什麼差別呢
----
Sent from
BePTT on my iPhone 11
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.97.138 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1639200005.A.6A1.html
2F：→ VF84: 你參考看看 12/11 14:03
3F：推 VF84: TL;DR: 因為 u1v2 和 u2v1 的位移都是 n/2，所以併在一起算 12/11 14:16
4F：→ j12345453: 請問為何前半段的u1 v1反而不成上權重呢 12/11 14:42
5F：→ j12345453: 後半段的數比較小反而乘上權重 12/11 14:42
6F：推 VF84: 因為 u1v1 不用位移呀 12/11 14:44
8F：→ VF84: 阿，我好像知道我哪裡弄混你了 12/11 14:50
9F：→ VF84: 我的算式裡 u2 和 v2 是比較高的位元 12/11 14:50
10F：→ VF84: 跟題目反過來 12/11 14:51
11F：→ j12345453: 阿我懂了 謝謝大大講解 12/11 14:55
12F：→ j12345453: 你是把U2 V2當作前半段對吧 12/11 14:55
13F：推 VF84: 嘿嘿沒錯 12/11 14:56
14F：→ j12345453: 那我另外想請問 12/11 14:57
15F：→ j12345453: 我貼文的圖片裡 12/11 14:57
16F：→ j12345453: 最後Merge階段是thetaN 12/11 14:57
17F：→ j12345453: 那是因為各but相加嗎 12/11 14:57
18F：推 VF84: 可以這樣說。在利用遞迴算出那三組算式後，剩下的就只剩加 12/11 14:59
19F：→ VF84: 減法跟位元位移的運算了，這些可以在 theta(N) 內算出 12/11 14:59
20F：→ j12345453: Bit 12/11 15:02
21F：→ j12345453: 不過感覺這題最Tricky的地方是在 12/11 15:05
22F：→ j12345453: 我怎麼想的到u1v2+u2v1 可以用(u1+u2 )(v1+v2)乘出來 12/11 15:05
23F：→ j12345453: 雖然這不是很難 12/11 15:05
24F：→ j12345453: 但一開始真的想不到可以這樣 12/11 15:05
25F：推 VF84: 我 conquer 這題的思考過程，是先用最原始的方法算，然後看 12/11 15:07
26F：→ VF84: 哪裡是可以化簡的。 12/11 15:07
27F：→ VF84: 再來就是靠想像力了 12/11 15:08
28F：推 VF84: 分解再重組，鋼之鍊金術師都有教 12/11 15:10
29F：推 NCTUCKCurry: 我的想法是u1v2和u2v1的位移量是一樣的 所以可以直接 12/11 16:25
30F：→ NCTUCKCurry: 算他們的和 12/11 16:25
31F：推 joywilliamjo: karatsuba變形吧，當場沒看過真的很難想到 12/11 20:35