演算法 Divide and conquer

[j12345453 (CJentalL)]

 https://i.imgur.com/cAHPDBO.jpg

如題
清大這題把Bit切分成前後半
又特別講解要做出u1v2+u2v1
原因是什麼呀

這樣跟u1v1直接乘有什麼差別呢
----
Sent from BePTT on my iPhone 11

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.97.138 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1639200005.A.6A1.html
推 VF84: https://imgur.com/a/mSGW38E
→ VF84: 你參考看看
推 VF84: TL;DR: 因為 u1v2 和 u2v1 的位移都是 n/2，所以併在一起算
→ j12345453: 請問為何前半段的u1 v1反而不成上權重呢
→ j12345453: 後半段的數比較小反而乘上權重
推 VF84: 因為 u1v1 不用位移呀
推 VF84: https://imgur.com/a/OxCOHgm
→ VF84: 阿，我好像知道我哪裡弄混你了
→ VF84: 我的算式裡 u2 和 v2 是比較高的位元
→ VF84: 跟題目反過來
→ j12345453: 阿我懂了 謝謝大大講解
→ j12345453: 你是把U2 V2當作前半段對吧
推 VF84: 嘿嘿沒錯
→ j12345453: 那我另外想請問
→ j12345453: 我貼文的圖片裡
→ j12345453: 最後Merge階段是thetaN
→ j12345453: 那是因為各but相加嗎
推 VF84: 可以這樣說。在利用遞迴算出那三組算式後，剩下的就只剩加
→ VF84: 減法跟位元位移的運算了，這些可以在 theta(N) 內算出
→ j12345453: Bit
→ j12345453: 不過感覺這題最Tricky的地方是在
→ j12345453: 我怎麼想的到u1v2+u2v1 可以用(u1+u2 )(v1+v2)乘出來
→ j12345453: 雖然這不是很難
→ j12345453: 但一開始真的想不到可以這樣
推 VF84: 我 conquer 這題的思考過程，是先用最原始的方法算，然後看
→ VF84: 哪裡是可以化簡的。
→ VF84: 再來就是靠想像力了
推 VF84: 分解再重組，鋼之鍊金術師都有教
推 NCTUCKCurry: 我的想法是u1v2和u2v1的位移量是一樣的 所以可以直接
→ NCTUCKCurry: 算他們的和
推 joywilliamjo: karatsuba變形吧，當場沒看過真的很難想到