PTT數位生活區 / Python

[問題] 超 大數次方運算

看板Python作者時間6年前 (2019/02/26 13:33), 6年前編輯推噓5(5推 0噓 16→)
留言21則, 6人參與, 6年前最新討論串1/1
最近發現 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://www.ptt.cc/bbs/Python/M.1551159184.A.CEE.html 連結修正 ※ 編輯: nevikw39 (77.73.67.86), 02/26/2019 13:34:49
→
02/26 20:24, 6年前 , 1F
建表查表會不會比較快？
02/26 20:24, 1F
建什麼表呢？ ※ 編輯: nevikw39 (106.107.176.158), 02/26/2019 22:07:20
→
02/26 22:43, 6年前 , 2F
Divide and Conquer: a^20 == (a^2)^10 == (a ^4) ^5
02/26 22:43, 2F
→
02/26 22:46, 6年前 , 3F
不確定這思考方向對不對
02/26 22:46, 3F
→
02/26 23:29, 6年前 , 4F
我思考方向好像是錯的 因為算根本沒花多少時間= =
02/26 23:29, 4F
推
02/26 23:42, 6年前 , 5F
你有學過快速冪嗎 演算法課本去翻一翻 概念不難
02/26 23:42, 5F
推
02/26 23:45, 6年前 , 6F
python占便宜 哈哈哈
02/26 23:45, 6F
推
02/26 23:46, 6年前 , 7F
剛剛我寫了個快速冪然後就TLE了，我覺得應該是python IO太
02/26 23:46, 7F
→
02/26 23:47, 6年前 , 8F
慢
02/26 23:47, 8F
我也覺得是輸出太慢 可是直接寫到 stdout.buffer 也沒有比較快
→
02/27 00:02, 6年前 , 9F
time python -c "str(pow(10**5,10**5))" 要七秒
02/27 00:02, 9F
→
02/27 00:02, 6年前 , 10F
user 0m7.812s
02/27 00:02, 10F
→
02/27 00:02, 6年前 , 11F
都花在轉字串...
02/27 00:02, 11F
→
02/27 00:04, 6年前 , 12F
如果自幹的算法比 python 內建還快不就取代掉惹
02/27 00:04, 12F
Python 到底有沒有什麼特殊解呢？ 不然自己寫大數用 c++ 應該更有效率 字串的部分查了一下，% > .format > str() 的樣子，可是還是 4.8 秒 ※ 編輯: nevikw39 (106.107.176.158), 02/27/2019 00:18:20
推
02/27 02:21, 6年前 , 13F
菜雞連AC都寫不出QQ
02/27 02:21, 13F
a 大你好，第一題我是有 AC 喇，只是很好奇其他人怎麼有辦法速解，如果你有好方法還請 不吝分享 ※ 編輯: nevikw39 (101.136.64.8), 02/27/2019 07:47:44
推
02/27 11:08, 6年前 , 14F
那如果試試這個？https://www.python123.io/index/
02/27 11:08, 14F
→
02/27 11:09, 6年前 , 15F
topics/algorithm_100_days/100-days-of-algorithm
02/27 11:09, 15F
→
02/27 11:09, 6年前 , 16F
s-10
02/27 11:09, 16F
Karatsuba 法似乎多用於乘法，然後再用迴圈，回去試試有沒有比較快 ※ 編輯: nevikw39 (101.137.163.39), 02/27/2019 17:31:11
→
02/27 22:41, 6年前 , 17F
from decimal import *; getcontext().prec=700000;
02/27 22:41, 17F
→
02/27 22:41, 6年前 , 18F
print(Decimal(10**5) ** (10**5))
02/27 22:41, 18F
實在非常感謝 e 大提供的想法，沒想到 decimal 也可以這麼用 只是你應該是指 Decimal(a) ** Decimal(b) ，醬子才是 decimal 的運算 XD ※ 編輯: nevikw39 (106.107.176.158), 02/28/2019 08:30:42
→
02/28 13:04, 6年前 , 19F
上面 e 大寫法沒有問題，decimal 實作上有 type casting
02/28 13:04, 19F
→
02/28 13:08, 6年前 , 20F
02/28 13:08, 20F
→
02/28 13:10, 6年前 , 21F
3.4 https://goo.gl/QNofY9，可以從 Decimal.__pow__ 查
02/28 13:10, 21F
‣ 更多 nevikw39 的文章
文章代碼(AID): #1STC-Gpk (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 nevikw39 的文章
文章代碼(AID): #1STC-Gpk (Python)