作者nevikw39
看板Python
標題[問題] 超 大數次方運算
時間Tue Feb 26 13:32:58 2019
最近發現 Python 的整數型別原來沒有上限，對於大數的支援實在非常完善，甚至幾十位數
相乘都能幾乎瞬間求得答案，所以就想挑戰一些大數的題目，像是這題：
http://bit.ly/2H7QGHo
我是直接 a ** b 喇，這樣花了 4.8 秒。然後我就在想如何改進。先 sum = a ** (b // 2
)，再 sum *= 2，如果 b 是奇數再乘 a。但是如此一來反而要花 6.8 秒！
輸出的部分也有嘗試直接寫入 stdout.buffer 還是 4.8 秒
同一題一樣 Python 有人原本 4.7 秒變成 78 毫秒，到底怎麼辦得到啊？
下一題（
http://bit.ly/2H1TuGc）測資更變態，提示說 Python 有特殊解法第一題可以在
0.1 秒內解出，第二題 Python 也有人在 0.5 秒內解出
先謝謝各位大大惹
--
Sent from my Sony Xperia XZ1
○ PiTT // PHJCI
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 77.73.67.86
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1551159184.A.CEE.html
連結修正
※ 編輯: nevikw39 (77.73.67.86), 02/26/2019 13:34:49
1F：→ s860134: 建表查表會不會比較快？02/26 20:24
建什麼表呢？
※ 編輯: nevikw39 (106.107.176.158), 02/26/2019 22:07:20
2F：→ s860134: Divide and Conquer: a^20 == (a^2)^10 == (a ^4) ^502/26 22:43
3F：→ s860134: 不確定這思考方向對不對02/26 22:46
4F：→ s860134: 我思考方向好像是錯的 因為算根本沒花多少時間= =02/26 23:29
5F：推 alan23273850: 你有學過快速冪嗎 演算法課本去翻一翻 概念不難02/26 23:42
6F：推 nini200: python占便宜 哈哈哈02/26 23:45
7F：推 oToToT: 剛剛我寫了個快速冪然後就TLE了，我覺得應該是python IO太02/26 23:46
8F：→ oToToT: 慢02/26 23:47
我也覺得是輸出太慢 可是直接寫到 stdout.buffer 也沒有比較快
9F：→ s860134: time python -c "str(pow(10**5,10**5))" 要七秒02/27 00:02
10F：→ s860134: user 0m7.812s02/27 00:02
11F：→ s860134: 都花在轉字串...02/27 00:02
12F：→ s860134: 如果自幹的算法比 python 內建還快不就取代掉惹02/27 00:04
Python 到底有沒有什麼特殊解呢？
不然自己寫大數用 c++ 應該更有效率
字串的部分查了一下，% > .format > str() 的樣子，可是還是 4.8 秒
※ 編輯: nevikw39 (106.107.176.158), 02/27/2019 00:18:20
13F：推 alen84204: 菜雞連AC都寫不出QQ02/27 02:21
a 大你好，第一題我是有 AC 喇，只是很好奇其他人怎麼有辦法速解，如果你有好方法還請
不吝分享
※ 編輯: nevikw39 (101.136.64.8), 02/27/2019 07:47:44
15F：→ alan23273850: topics/algorithm_100_days/100-days-of-algorithm02/27 11:09
16F：→ alan23273850: s-1002/27 11:09
Karatsuba 法似乎多用於乘法，然後再用迴圈，回去試試有沒有比較快
※ 編輯: nevikw39 (101.137.163.39), 02/27/2019 17:31:11
17F：→ edwar: from decimal import *; getcontext().prec=700000;02/27 22:41
18F：→ edwar: print(Decimal(10**5) ** (10**5)) 02/27 22:41
實在非常感謝 e 大提供的想法，沒想到 decimal 也可以這麼用
只是你應該是指 Decimal(a) ** Decimal(b) ，醬子才是 decimal 的運算 XD
※ 編輯: nevikw39 (106.107.176.158), 02/28/2019 08:30:42
19F：→ s860134: 上面 e 大寫法沒有問題，decimal 實作上有 type casting 02/28 13:04