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

[tropical72 (藍影)]

※ 引述《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:我很好奇，為什麼2進位轉換10進位會花很多時間？
→ iamstudent:不就是一直除以10和取餘數？
→ iamstudent:而且需要以10進位顯示，應該只有最後輸出給人看的時候
→ iamstudent:考慮大數最常見的使用環境，例如密碼學
→ iamstudent:過程中的運算速度才是考量重點
→ iamstudent:中間的運算量會遠超過輸出時的計算
推文補齊。一直除10和取餘數,不就又是另一個大數除法運算了嗎?
先做2進位版的大數,再做進制轉換的大數,應較耗時吧?
運算速度普遍性確實才是考量重點,特別點出來是因寫 acm 會有大量io,
反而不適合以2進位版做處理。

→ SmallBeeWayn:16進位用char來儲存呢?
也行啊！只是有意義嗎 Orz 處理次數比較少,char 資料型態基本運算時間又沒 int 快。
※ 編輯: tropical72      來自: 123.195.165.40       (03/16 15:57)
推 iamstudent:如果要用2進位就用unsigned int吧
→ buganini:剛好就是bcmath和gmp兩種作法
→ buganini:不曉得bcmath實際上是除存什麼，不過在PHP裡面bcmath的
→ buganini:輸入輸出都是字串，而gmp除了轉成字串的函數之外，其他都
→ buganini:是return一個resource
推 Slither:以前不是有個東西叫BCD嘛.. instruction set 也有 能用嗎?
推 Bencrie:我也覺得很奇怪這串怎麼沒人提 BCD ... 它被淘汰了嗎 XD
推 LPH66:BCD 就是文中提的用 char 的十進位大數...
→ MOONRAKER:BCD技術上跟十進位一次一位的處理差不多
→ MOONRAKER:可惡比樓上慢 XD
推 LPH66:XD
推 Slither:應該是有小小差異吧 BCD好像是一個數字是一個 nibble
→ Slither:(喔 那是所謂 packed BCD) 算了算了 看起來太古早了XD
推 mms:好焦慮喔都看不懂= =
→ mms:不過謝謝各位前輩熱心指教