作者jellyfishuan (jellyfishuan)
看板C_and_CPP
標題[問題] 大數階乘運算
時間Thu Apr 27 16:52:27 2017
開發平台(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1493283149.A.B50.html
※ 編輯: jellyfishuan (140.118.138.73), 04/27/2017 16:53:29
1F：→ Hazukashiine: 樓下借我一顆水晶球04/27 16:53
2F：→ Hazukashiine: 都天大地大的學校惹 為什麼還不會問問題ㄋ04/27 16:55
因為整個程式碼在VS爆掉之後通通不見惹QQ
所以想說先把想法丟上來請教大家看看w
※ 編輯: jellyfishuan (140.118.138.73), 04/27/2017 16:57:05
3F：→ Hazukashiine: 哇靠... 通通不見還真的蠻屌的 屌 爆 了04/27 16:57
4F：→ Hazukashiine: 如果很懶的話就用 "GNU MP Bignum Library"04/27 16:59
5F：→ Hazukashiine: 至少不用想那些 trivial 的問題 有現成的庫可以用04/27 16:59
哦哦好的感謝大大提供的資訊!! 等等來參考一下
6F：推 jerryh001: string 不是有 length() 可以用？04/27 17:09
我知道有size，length等函數可以抓噢，是有點不太確定要怎麼抓出長度之後用長度去對
應到陣列裡面這樣，這部分我有點卡關
7F：推 tuyutd0505: 不限定使用第三方函式庫的話 推薦 GMP library 或 MPI04/27 17:10
8F：→ tuyutd0505: R library(在Win平台我覺得比較好裝) 精度是吃記憶體04/27 17:10
9F：→ tuyutd0505: 大小的 記憶體越大可以算得越多04/27 17:10
好的，謝謝大大!!!
10F：→ LPH66: 先給你個心理準備, 幾十萬階乘會有上百萬位數04/27 20:58
11F：→ LPH66: 就算四位一組 (順帶一提這裡是 10000 不是 9999)04/27 20:58
12F：→ LPH66: 還是會需要那麼大的一個陣列, 寫得出來不一定跑得出來04/27 20:59
所以果然想的不夠周全www
13F：→ pttworld: 以int的2147483647來說，二數相乘不能超過，所以取四位 04/27 21:23
14F：→ pttworld: 數是至多了。取餘是取一萬餘，不是9999。因為是到幾十04/27 21:23
15F：→ pttworld: 萬，乘法寫法必須每迴圈乘完做加總後的進位判斷，因為04/27 21:23
16F：→ pttworld: 加了幾十萬次有可能溢位，但如果只是幾千，9999的幾千04/27 21:23
17F：→ pttworld: 次也放得下，可全部乘完再一次進位處理。04/27 21:23
18F：→ pttworld: 如果覺得一般的乘法太慢，可以考慮傅立葉轉換的大數乘04/27 21:33
19F：→ pttworld: 法，不過花費記憶體多。04/27 21:33
哦哦哦感謝大大點出盲點!!!
20F：→ HamalAri: 10 萬階乘 43萬位，本人的洨筆電三秒就跑完，gmp很強的 04/27 23:25
21F：→ HamalAri: 洨筆電還只有 2g 呢 04/27 23:26
22F：→ HamalAri: 要相信發展了二十年的東西絕對比自幹的東西好04/27 23:26
好的謝謝板上大大們的提醒!!
我會去看完之後再來看怎麼解決的w
※ 編輯: jellyfishuan (140.118.138.42), 04/28/2017 02:50:29
23F：推 school4303: 連.cpp都不見？ 04/28 06:47
就消失了我找不到QQ 我猜可能路徑亂掉之類的吧就認份重寫了，還好還寫不多幾十行而
已
24F：→ MOONRAKER: 還 滿 屌 的 屌 爆 了 04/28 10:18
25F：→ descent: 先把程式碼放在版本控制系統吧 04/28 10:54
26F：推 LPH66: >HamalAri 他現在就是要想自己寫, 那自己寫就會有這個問題04/28 14:35
27F：→ LPH66: 先不說 gmp, 光是大階乘我在幾年前就有看過快速實作 04/28 14:36
28F：→ LPH66: 那個做法在十幾年前的電腦十萬階乘也能幾秒內跑出來 04/28 14:40
30F：→ LPH66: 不過原 PO 只是要寫個期末 project 而且應該不用玩這麼大04/28 14:42
31F：→ LPH66: 而已* 04/28 14:42
32F：→ LPH66: 所以我只是要提醒原 PO 量力而為, 目標訂太大可能會失望 04/28 14:45
嗯嗯其實能過期末實習的就ok了
感謝大大翻出的舊檔案!!
※ 編輯: jellyfishuan (140.118.138.42), 04/28/2017 15:36:09