如何實現任意精度計算？

01-08

mathematica可以實現任意精度的計算，但不明白它是怎麼實現的，容易想到的是數組模擬，但C中長度最小的char是１個位元組，其中３個bit用不到，開銷太大惹。。。

內存中用256進位啊，就都用上了。最後列印出來的時候再轉。

為啥一定要用char？用int32或int64都可以。反正不管是誰寫的高精，都是要用數組的。具體用多少進位隨便了，浪費一兩個bit那都不是事兒。

內存中使用什麼變數類型（重點是幾個位元組）來作為單元、每個單元是多少進位，完全取決於你的需求。

OI 中有時候會用到簡單的高精度，運算不多，對速度和空間也沒什麼要求，但是有不少輸出、字元串相關的處理，很多時候就會選擇 char （一個位元組）來作為單元，十進位（一個單元就存 0~9 ）。

更多時候對運算速度和空間有一定要求，往往會選擇比較符合平台架構的 32 位或者 64 位變數類型來作為單元，2的整數次冪進位（例如 2^16 或 2^32 ，不溢出的前提下的最大值）。如此一來原本費時的進位操作（除、模）都變成位運算，而且也最大程度利用了空間。不過這樣在輸出的時候就要稍微多費些事兒做點轉換了。大部分的高精庫都是這麼實現的，畢竟庫只要寫一次。

我以前在 OI 中常用一種折中方案，用 32 位變數類型， 10000 進。浪費的空間不多，輸出的時候只要補零就行。唯一缺點就是慢，不過一般可以接受。

隨便找個大整數庫，看看人家怎麼實現的，不就知道了

不想轉的話就用按十進位切，8~9位一節，用int存的話，多少浪費一點點。

想充分利用的話就按二進位切，31~32位一節，可以充分利用int型。

位數用太盡的話，進位跟乘法的時候容易溢出，處理起來比較矯情。

能用盡int就夠了，速度上。

實現上最簡單的當然就是十進位一位一節，速度慢，內存浪費多，入門的時候用來領會領會。

High-Precision Software Directory