→ doom8199 : 最快的方法不是查表法嗎 (誤) 09/27 02:04
→ wohtp : 先看剛好可以分解得乾淨的次方 09/27 04:12
→ wohtp : 基本上你在做的是把 a^n 寫成 (a^p)^q 09/27 04:13
→ wohtp : 要求 pq = n，然後希望最小化 p+q 09/27 04:13
→ wohtp : 這就算幾不等式而已，所以最佳解是 p = q 09/27 04:14
→ wohtp : 拆不乾淨的話就盡可能做到最好，先處理最接近 n 的 09/27 04:16
→ wohtp : 完整平方數，餘數再用相同手法繼續 09/27 04:17
→ wohtp : 所以，如果你要問除以二是不是最快，很明顯不是 09/27 04:19
→ bjiyxo : 能否找到反例呢? 09/27 04:21
→ wohtp : 九次方就是啦 09/27 04:44
→ wohtp : 分成 (a^4)^2 * a 要做五次乘法 09/27 04:45
→ wohtp : (a^3)^3 只要四次 09/27 04:45
→ wohtp : 指數很大的話，類似技巧重複疊代多次又會更快 09/27 04:47
→ bjiyxo : (a^4)^2*a也是四次吧? 09/27 04:50
→ wohtp : 算到 a^4 要三次，平方再一次，乘以a再一次 09/27 04:52
→ wohtp : 五次 09/27 04:52
→ bjiyxo : (a^2)^2這樣只要兩次 09/27 04:53
→ wohtp : 因為你算 a^4 的時候疊代了第二層。 09/27 04:54
→ bjiyxo : 可能我沒有說清楚，不過這個演算法就是重複疊代的 09/27 04:55
→ bjiyxo : 抱歉 09/27 04:56
※ 編輯: bjiyxo (123.192.45.236), 09/27/2014 05:00:09
→ wohtp : 我的方法每一層都會比你快，但是可以疊代的層數比較 09/27 05:00
→ wohtp : 少 09/27 05:00
→ wohtp : 所以問題是層數的差距長得比較快，還是每一層的效率 09/27 05:01
→ wohtp : 差長得比較快...好麻煩 09/27 05:01
→ bjiyxo : 我當初的想法是看乘多少次，至於層好像很難比較? 09/27 05:02
→ bjiyxo : 如果只比較乘的次數這樣可以找反例嗎QQ 09/27 05:03
→ wohtp : 如果你限制只能做無腦疊代的話，我找到反例了 09/27 05:15
→ wohtp : 唉，好像算錯了 09/27 05:17
→ wohtp : 考慮 a^15 09/27 05:21
→ wohtp : 分成 (a^7)^2 * a ，借用上面 a^7 需要四次，一共要 09/27 05:22
→ wohtp : 做六次乘法 09/27 05:22
→ wohtp : 但是 (a^5)^3 只要五次 09/27 05:22
→ bjiyxo : 你說的對，這樣真的找到反例了，感謝！ 09/27 05:28
→ wohtp : 我的感覺是，指數很大的時候，二分法的層數優勢可能 09/27 05:32
→ wohtp : 會把其他的方法都淹過去 09/27 05:33
→ wohtp : 但是指數在只有幾十或幾百的時候就不一定 09/27 05:34
→ wohtp : 然後即使指數非常大，一些特定數字也有可能微調到比 09/27 05:35
→ wohtp : 二分法快一點點 09/27 05:35
推 jurian0101 : 搜尋 Addition-chain_exponentiation，是個意料之外 09/27 18:55
→ jurian0101 : 的難題，已經被證明找到須最少次乘法的鍊是NP完備。 09/27 18:55
→ jurian0101 : 而且這問題還出現在高德納的TAOCP第二冊某處，很有 09/27 18:56
→ jurian0101 : 文章的意思 09/27 18:56
推 jurian0101 : 更有趣是不止你說的D&C，連DP也無法找。 09/27 19:01
→ suhorng : 那如果只考慮時間複雜度，不算確切的數字呢？ 09/27 21:37
→ doom8199 : 我覺得原po應該要改標題: 如何用最少乘法拆解 a^N 09/27 23:43
→ doom8199 : 找到最少乘法數量,不代表計算時間最短 09/27 23:44
→ doom8199 : 站在軟硬體角度想, computing time 跟 chip area 09/27 23:47
→ doom8199 : 是 trace-off, 只要提高成本, a^3 是能算的跟 a^2 09/27 23:48
→ doom8199 : 幾乎一樣快 09/27 23:48