[問題] 請問大數除以大數演算法？

看板Prob_Solve作者 (藍影)時間15年前 (2010/10/06 04:27), 編輯推噓4(4推 0噓 17→)
留言21則, 5人參與, 最新討論串1/1
大數目前我只做得出 加減乘除 大數 除以 大數 我卻卡住了 不知是否有參考的演算法可解決？ 謝謝各位，感激不盡!! -- 如果沒有明天 我想見你最後一面.. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.142
推
10/06 10:35, , 1F
直式除法?
10/06 10:35, 1F
→
10/06 13:49, , 2F
直式除法我想過，假設是BigA/BigB, 實現上似乎有困難
10/06 13:49, 2F
→
10/06 13:50, , 3F
google 後，大多寫到div時，都只寫BigA/int,所以有疑惑
10/06 13:50, 3F
推
10/06 14:05, , 4F
大整數除法，以直式除法觀點去走，就會用上大數乘與減
10/06 14:05, 4F
→
10/06 14:06, , 5F
然後就會發現之前寫的東西如果通用性夠，應該幾乎都會用上
10/06 14:06, 5F
→
10/06 15:10, , 6F
這部份我再仔細思考好了..謝謝各位的資訊.
10/06 15:10, 6F
→
10/06 16:44, , 7F
如果您會寫大數減大數，那麼直式除法難不倒你。
10/06 16:44, 7F
→
10/06 17:38, , 8F
加減乘的確都寫完了,除法還在try..
10/06 17:38, 8F
推
10/08 22:50, , 9F
的確是直式除法。當然也可以二分搜，十分逼近，各有利弊。
10/08 22:50, 9F
→
10/08 23:32, , 10F
= = 我目前的確是用二分搜，但我覺得速度很慢耶!!
10/08 23:32, 10F
→
10/08 23:39, , 11F
但是都寫出+-*了, 要且直式除法應該不難XD ?
10/08 23:39, 11F
→
10/08 23:39, , 12F
噢還有就是 二分搜不用每次都乘一次喔
10/08 23:39, 12F
→
10/08 23:40, , 13F
寫是寫出來了,只是覺得用二分搜似乎不快,在想是不是有
10/08 23:40, 13F
→
10/08 23:40, , 14F
人有提出什麼演算法能加快其除法之速度..
10/08 23:40, 14F
→
10/09 00:35, , 15F
不用每次都乘一次的意思是？目前我是推斷答案位數超過
10/09 00:35, 15F
→
10/09 00:36, , 16F
3位數時，我就直接從1-9乘完，到時再用2分法比大小取
10/09 00:36, 16F
→
10/09 00:36, , 17F
適當之商值
10/09 00:36, 17F
推
10/09 08:00, , 18F
不用每次都乘一次的意思是說，第一次猜測商，乘完之後，
10/09 08:00, 18F
→
10/09 08:01, , 19F
由於每次是(L+R)/2, 所以乘法出來的值也可以類推, 用加減
10/09 08:01, 19F
→
10/09 08:01, , 20F
以及除以2來做，不必每次都做一次乘法 (不一定比較快)
10/09 08:01, 20F
→
10/09 08:29, , 21F
大致上知道該怎麼做了,謝謝s大的細心解說,再次感謝!!
10/09 08:29, 21F
‣ 更多 tropical72 的文章
文章代碼(AID): #1Cguf1MA (Prob_Solve)