Re: [問題] 用多少位元來儲存多少位十進位數會最省記憶體？

看板C_and_CPP作者tropical72 (藍影)時間12年前 (2012/03/16 15:40)推噓8(8推 0噓 14→)

留言22則, 8人參與討論串2/2 (看更多)

※ 引述《mms (說你愛我)》之銘言： : 2.我要怎麼知道我計算機裏標準輸入串流的緩衝空間是幾位元？ : 那麼，究竟在實作的時候對於一串十進位數怎麼切怎麼存會是最好的？ : 以一個例子來看，假設要對1234567890123456789作任意基底的數制轉換， : 要用什麼樣的資料型態，對數字做怎麼樣的分割會比較好？你的問題讓人不知道該怎麼回答才好，因為這個答案相依於，大數到底要用幾進制做處理，才能回答用怎樣資料型態為佳，提到「作任意基底數制轉換」，我想沒標準答案了。如果這是作業的話，我想你們老師要的答案大概是在萬進制情況上，使用 int。這個先參考一下 http://0rz.tw/G6kJI 。另外目前能 google 到的大數演算法，大概只能算是玩具級而已，自己拿來當練習ok，要實際用的話可能要再審慎評估。 ( acm 的話是納到練習裡面去 ) 若要包成 class 使用時，牽扯到 shallow copy, deep copy 對速度/記憶體之影響，可看這篇文章之回覆 http://0rz.tw/Ons3G (主文講的大概都是垃圾廢話)。真正要好、要快的，大概要去翻 introduction to algorithm 出來實作，沒記錯的話裡面提到的大數乘法關係到了 fourier transform。只是要「觀摩」簡單方式的話，其實有不少 source code 可參考，精華區記得有，甚至還有 gmp 大數庫。再回到你的問題，目前就我所知並沒有兩全的方式，每種進位方式都有優缺點，這必須自己評估。 1. 10進位基本上10進位還是可以用，只是大數宣告時資料型態採用 char big[BUFSIZ]; 這樣下來並不會浪費太多空間，反而「趨近」於最省空間的方式，但很遺憾的，它在乘法裡完全不能使用一次性進位，且一次只能處理一個 dig，速度很慢，實際上只是拿來給初學者做引言用而已。 2. 10^n 進位目前所有的基本資料型態 (POD) 裡，處理速度最快的是 int 資料型態，而不是 char、long int、unsigned xxx 等，此種架構採用的是 int big[BUFSIZE]; 但 n 應該選多少？如果考慮乘法問題的話，拿二個最大的元素做相乘，再考慮有進位，初算式如下 : 10 進位 -> 10*10 = 10 ** 2 ---> char 範圍 100 進位 -> 100*100 = 10 ** 4 ---> short int 範圍 1000 進位 -> 1000*1000 = 10 ** 6 10000 進位 -> 10000*10000= 10 ** 8 ---> int 範圍到十萬進位的話=10**10 > INT_MAX，所以會選萬進位。但上述的問題還是回歸到, 要用幾進制的問題。不過除了 10 進位之外，百進位、千進位、萬進位在從「輸入」轉「大數」，要花多一點點時間處理。萬進位可用一次性進位，在乘法上除非連續出現 (9999 * 9999) 約 20 次，使用一次性進位才會出包 (可細思為什麼)。 3. 2^n 進位一種想法是，電腦本身對於 bitwise 之操作較為擅長，單純處理大數使用 2^n 速度比 10^n 進位快很多。故以 2^15 / 2^16 進位做處理，2^15 = 32768，比一萬還大； 2^16 = 65536，也比一萬還大。選用 32768 原因是到時宣告成 int，在減、除法時可暫時出現負數；選用 65536 原因是到時宣告成 unsigned，在加、乘法時運算次數會更少。 2^n 這種想法其實不少人有想到，但實作上其實較為繁鎖、複雜，原因在於輸入從 10 進位之字串，轉存成 int big[BUFSIZ]，或從 int bug[BUFSIZ] 輸出，中間做的轉換其實很慢，甚至光是轉換時間，10^n 進位可能就做完運算。但好處是加、減、乘、除、幕次速度都很快。再進一步試想，若有大量 I/O 時，並不建議使用 2^n 做為進制運作，因為光是轉換所費時間往往比運算時間還長很多；反之若 IO 次數較少時，使用 2^n 進位是可行的，速度上也較佔上風。很多廢話，只是想引述出，問題似乎沒一個標準答案 (至少我是這麼看的)。 -- 我知道 ~ 但別說出來 , 說出來讓人感到特別難過... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.165.40

推

iamstudent

03/16 15:47, , 1^F

03/16 15:47, 1^F

→

iamstudent

03/16 15:48, , 2^F

03/16 15:48, 2^F

→

iamstudent

03/16 15:49, , 3^F

03/16 15:49, 3^F