[問題] 大數階乘運算

看板C_and_CPP作者 (jellyfishuan)時間8年前 (2017/04/27 16:52), 8年前編輯推噓4(4推 0噓 28→)
留言32則, 9人參與, 最新討論串1/1
開發平台(Platform): (Ex: Win10, Linux, ...) win10 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) Visual Studio 2015 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： 各位版大好,小弟目前得寫大數計算機,期末實習的project QQ 然後目前卡在階乘的部分惹,網路上搜尋發現大部分資料皆為幾十上百的階乘 例如50!或170!之類的 但我們的大數計算機希望能做到真正的大數那種可能可以處理幾十萬!的 然後現在有個方向是字串讀入輸入的數字 輸入的數字可能過大而int塞不下 然後分解4位並透過stringstream塞入int[8] int[0]~int[8] 每個陣列裡各有四位數字 舉例來說就是string(123456789012)會變int[0]=1234,int[1]=5678,int[2]=9012這樣 然後再透過int陣列去做階乘 答案的int矩陣假如計算後大於9999, 則int[7]=int[8]/9999,int[8]=int[8]%9999; But 卡在不知道如何去抓input的長度從而可以塞入陣列裡面 試著編譯過之後 VS的整個專案廢掉說不給用 出現out of range然後說什麼檔案已消失之類的QQ 發問是希望有大大可以指點一下QQ 並順便看一下想的方向正確嗎 因為做到現在有點疑惑,感覺寫到一半覺得方向好像有點 錯Q -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.118.146.57 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1493283149.A.B50.html ※ 編輯: jellyfishuan (140.118.138.73), 04/27/2017 16:53:29
→
04/27 16:53, , 1F
樓下借我一顆水晶球
04/27 16:53, 1F
→
04/27 16:55, , 2F
都天大地大的學校惹 為什麼還不會問問題ㄋ
04/27 16:55, 2F
因為整個程式碼在VS爆掉之後通通不見惹QQ 所以想說先把想法丟上來請教大家看看w ※ 編輯: jellyfishuan (140.118.138.73), 04/27/2017 16:57:05
→
04/27 16:57, , 3F
哇靠... 通通不見還真的蠻屌的 屌 爆 了
04/27 16:57, 3F
→
04/27 16:59, , 4F
如果很懶的話就用 "GNU MP Bignum Library"
04/27 16:59, 4F
→
04/27 16:59, , 5F
至少不用想那些 trivial 的問題 有現成的庫可以用
04/27 16:59, 5F
哦哦好的感謝大大提供的資訊!! 等等來參考一下
推
04/27 17:09, , 6F
string 不是有 length() 可以用？
04/27 17:09, 6F
我知道有size，length等函數可以抓噢，是有點不太確定要怎麼抓出長度之後用長度去對 應到陣列裡面這樣，這部分我有點卡關
推
04/27 17:10, , 7F
不限定使用第三方函式庫的話 推薦 GMP library 或 MPI
04/27 17:10, 7F
→
04/27 17:10, , 8F
R library(在Win平台我覺得比較好裝) 精度是吃記憶體
04/27 17:10, 8F
→
04/27 17:10, , 9F
大小的 記憶體越大可以算得越多
04/27 17:10, 9F
好的，謝謝大大!!!
→
04/27 20:58, , 10F
先給你個心理準備, 幾十萬階乘會有上百萬位數
04/27 20:58, 10F
→
04/27 20:58, , 11F
就算四位一組 (順帶一提這裡是 10000 不是 9999)
04/27 20:58, 11F
→
04/27 20:59, , 12F
還是會需要那麼大的一個陣列, 寫得出來不一定跑得出來
04/27 20:59, 12F
所以果然想的不夠周全www
→
04/27 21:23, , 13F
以int的2147483647來說，二數相乘不能超過，所以取四位
04/27 21:23, 13F
→
04/27 21:23, , 14F
數是至多了。取餘是取一萬餘，不是9999。因為是到幾十
04/27 21:23, 14F
→
04/27 21:23, , 15F
萬，乘法寫法必須每迴圈乘完做加總後的進位判斷，因為
04/27 21:23, 15F
→
04/27 21:23, , 16F
加了幾十萬次有可能溢位，但如果只是幾千，9999的幾千
04/27 21:23, 16F
→
04/27 21:23, , 17F
次也放得下，可全部乘完再一次進位處理。
04/27 21:23, 17F
→
04/27 21:33, , 18F
如果覺得一般的乘法太慢，可以考慮傅立葉轉換的大數乘
04/27 21:33, 18F
→
04/27 21:33, , 19F
法，不過花費記憶體多。
04/27 21:33, 19F
哦哦哦感謝大大點出盲點!!!
→
04/27 23:25, , 20F
10 萬階乘 43萬位，本人的洨筆電三秒就跑完，gmp很強的
04/27 23:25, 20F
→
04/27 23:26, , 21F
洨筆電還只有 2g 呢
04/27 23:26, 21F
→
04/27 23:26, , 22F
要相信發展了二十年的東西絕對比自幹的東西好
04/27 23:26, 22F
好的謝謝板上大大們的提醒!! 我會去看完之後再來看怎麼解決的w ※ 編輯: jellyfishuan (140.118.138.42), 04/28/2017 02:50:29
推
04/28 06:47, , 23F
連.cpp都不見？
04/28 06:47, 23F
就消失了我找不到QQ 我猜可能路徑亂掉之類的吧就認份重寫了，還好還寫不多幾十行而 已
→
04/28 10:18, , 24F
還 滿 屌 的 屌 爆 了
04/28 10:18, 24F
→
04/28 10:54, , 25F
先把程式碼放在版本控制系統吧
04/28 10:54, 25F
推
04/28 14:35, , 26F
>HamalAri 他現在就是要想自己寫, 那自己寫就會有這個問題
04/28 14:35, 26F
→
04/28 14:36, , 27F
先不說 gmp, 光是大階乘我在幾年前就有看過快速實作
04/28 14:36, 27F
→
04/28 14:40, , 28F
那個做法在十幾年前的電腦十萬階乘也能幾秒內跑出來
04/28 14:40, 28F
→
04/28 14:41, , 29F
剛剛挖了挖舊檔案翻了出來: http://tinyurl.com/koz86e5
04/28 14:41, 29F
→
04/28 14:42, , 30F
不過原 PO 只是要寫個期末 project 而且應該不用玩這麼大
04/28 14:42, 30F
→
04/28 14:42, , 31F
而已*
04/28 14:42, 31F
→
04/28 14:45, , 32F
所以我只是要提醒原 PO 量力而為, 目標訂太大可能會失望
04/28 14:45, 32F
嗯嗯其實能過期末實習的就ok了 感謝大大翻出的舊檔案!! ※ 編輯: jellyfishuan (140.118.138.42), 04/28/2017 15:36:09
‣ 更多 jellyfishuan 的文章
文章代碼(AID): #1P0R5DjG (C_and_CPP)