數(shù)組型高精度數(shù)詳解

1、.數(shù)組型高精度數(shù)詳解By Nettle一、高精度簡介二、高精度數(shù)三、高精度數(shù)與整型的運算四、高精度數(shù)與高精度數(shù)的運算五、高精度數(shù)的進制轉(zhuǎn)換六、高精度冪運算七、壓位高精度數(shù)一、高精度簡介 首先要知道在計算機里面每一種數(shù)據(jù)類型都有自己的存儲量。由于存儲量的限制所以都有著各自的精度，下面是一些常用數(shù)據(jù)類型的精度：以Pascal為例 整型的精度就是在該類型范圍內(nèi)所有的數(shù)。整型范圍Shortint-128 127Integer-32768 32767Longint-2147483648 2147483647Int64-9223372036854775808 9223372036854775807Byte

2、0 255Word0 65535Longword0 4294967295Qword0 18446744073709551615實型的精度是指當該類型的數(shù)據(jù)位數(shù)超過精度范圍時自動對超過的部分進行四舍五入。比如將 1234567890123 存入 real 時就會變?yōu)?1.234568E12，后面的890123 被四舍五入，只保留了位數(shù)。實型范圍精度real2.9E-39 1.7E3811至12single1.5E-45 3.4E387至8double5.0E-324 1.7E30815至16但是在某些計算中，參與運算的數(shù)的范圍大大超出了標準數(shù)據(jù)類型（整型，實型）能表示的范圍的運算，例如求兩個10

3、0位數(shù)的和的精確值。如果用一個整型變量，無論如何也是存儲不了的，用實型則會造成數(shù)據(jù)的不精確。于是，我們想到了辦法，將這個數(shù)字拆開，拆成一位一位的或者是四位四位的存儲到一個數(shù)組中，用一個數(shù)組去表示一個數(shù)字，這樣表示的數(shù)字就被稱為高精度數(shù)。對于高精度數(shù)，也要像平常數(shù)一樣做加減乘除以及乘方的運算，于是就有了高精度算法。二、高精度數(shù)高精度數(shù)的定義 高精度數(shù)事實上就是一個整型數(shù)組，根據(jù)題目中用的數(shù)據(jù)的位數(shù)設(shè)定數(shù)組的大小。為了方便通常將高精度數(shù)創(chuàng)建為一個新類型，如下：C+Pascaltypedef int hp250;type hp = array 0.250 of integer;此時hp a或 a:

4、hp就表示a為hp類型即大小為250的int數(shù)組。在本文中a0將存儲高精度數(shù)的位數(shù)，而從a1到aa0分別從低位到高位存儲高精度數(shù)的每一位數(shù)（這樣每當一位超過9時，會向前一進位的高精度數(shù)，為十進制高精度數(shù)）。未使用的部分均為0。例如將123456789012存入a中為數(shù)組下標012345678910111213存儲數(shù)據(jù)1221098765432100則a表示一個12位數(shù)，從右至左分別為210987654321。高精度數(shù)的讀入 高精度數(shù)一般采用字符串的方式，也可以采用字符的方式（以回車符作為結(jié)束的標志）。非讀入型的高精度數(shù)，同常賦值為a0 = a1 = 1 （多用于乘法）或 a0 = 1, a1

5、= 0（多用于加減）下面為字符串式的讀入（十進制）： 字符串，特別說明C+里字符串以下標0開始，Pascal以1開始。 C+Pascalvoid Init(hp &a)string s;int l; memset(a, 0, sizeof(a); /清零 cin >> s; l = s.size(); /得到數(shù)的位數(shù) for (int i = l; i >= 1; i-) ai = sl - i - '0' a0 = l; return ;procedure Init(var a: hp);var s: string; l, i: integer;be

6、gin fillchar(a, sizeof(a), 0); /清零 readln(s); l = length(s); for i := l downto 1 do ai := ord(sl i + 1) ord('0'); a0 := l;end;高精度進位 當 ai上的數(shù)據(jù)大于等于10的時候，就要向高位進位了。因為該數(shù)組中下標越大，位數(shù)越高，故對ai位進行進位的操作為： C+Pascalai + 1 = ai / 10;ai + 1 := ai div 10;ai %= 10ai := ai mod 10; 如果aa0位也大于等于10，在進位的同時就要考慮a0的值的改變了

7、。本文的處理方式是先估計a0能改變的最大值，再依次減小，直到達到準確位數(shù)。 C+Pascall = a0 + MAX;while (al = 0 && l > 1) l-;a0 = l;l := a0 + MAX;while (al = 0 and l > 1) do dec(l);a0 := l; 高精度退位當 ai上的數(shù)據(jù)小于0的時候，就要由高位退位了。因為該數(shù)組中下標越大，位數(shù)越高，故當ai位小于0時，ai + 1位退位的操作（以十進制為例）為： C+Pascalai + 1-;dec(ai + 1);ai += 10ai := ai + 10; 如果aa0位

8、等于0，在退位的同時就要考慮a0的值的改變了。此時要減小a0，直到達到準確位數(shù)。 C+Pascalwhile (aa0 = 0 && a0 > 1) a0-;while (aa0 = 0 and a0 > 1) do dec(a0); 一般的當被減數(shù)小于減數(shù)時，會交換兩數(shù)，所以不會出現(xiàn)結(jié)果為負數(shù)的情況。高精度數(shù)的輸出 從aa0開始遞減輸出，直到a1: C+Pascalvoid prin(hp a) for (int i = a0; i >= 1; i-) cout << ai; cout << endl;return ;procedur

9、e Prin(a: hp)var i: integer;begin for i := a0 downto 1 do write(ai); writeln;end;三、高精度數(shù)與整型的運算從這里開始，本文只寫出C+的算法，使用Pascal的OIers若有不懂的地方，可參照前面幾個對比的代碼進行理解，未出現(xiàn)過的代碼，本文會注明。以下代碼中a為參與運算的高精度數(shù)，b為結(jié)果。高精度數(shù)加整型 高精度數(shù)加整型有兩種算法： 一是將整型加到a1后，再不斷進位，直到ai小于10為止。但是如果a1+x就已經(jīng)溢出整型的范圍的話，就需要a1+x%10，a2+x/10后再進位。 另一種就是把x的每一位加到對應(yīng)位上再統(tǒng)一

10、進位。 相對而言第一種方法用的最多，因為特殊情況出現(xiàn)的很少。 代碼如下：/第一種void add_int(hp a, int x, hp &b)hp tmp; memcpy(tmp, a, sizeof(tmp);/復(fù)制a到tmp中int l = 1; tmp1 += x; while (tmpl > 9) tmpl + 1 += tmpl / 10; tmpl %= 10; l+; /inc(i) if (l > tmp0) tmp0 = l; memcpy(b, tmp, sizeof(b); return ;/第二種void add_int(hp a, int x,

11、hp &b)hp tmp; memcpy(tmp, a, sizeof(tmp);int l = 0; while (x) l+, tmpl += x % 10, x /= 10; l = max(tmp0, l); for (int i = 1; i <= l; i+) if (tmpi > 9) tmpi + 1+, tmpi -=10; l+; while (tmpl = 0 && l > 1) l-; tmp0 = l;memcpy(b, tmp, sizeof(b); return ;高精度數(shù)減整型 高精度數(shù)減整型，若高精度數(shù)小于整型，我個人

12、建議就不用高精度，把高精度轉(zhuǎn)化為整型直接減。這里只討論高精度數(shù)大于整型。 將高精度數(shù)的對應(yīng)位同x對應(yīng)位相減，再進行退位。void sub_int(hp a, int x, hp &b)hp tmp; memcpy(tmp, a, sizeof(tmp);int l = 1; while (x) tmpl -= x % 10, x /= 10, l+; for (int i = 1; i <= tmp0; i+) if (tmpi < 0) tmpi += 10, tmpi + 1-; while (tmp0 = 0 && tmp0 > 1) tmp0-

13、;memcpy(b, tmp, sizeof(b);return ;高精度數(shù)乘整型 高精度數(shù)的每一位都乘上x，再逐一進位即可。要注意ai * x 不能超過整型范圍。int MAX = 10; / 整型最多10位void mul_int(hp &a, int x, hp &b)hp tmp; memset(tmp, 0, sizeof(tmp); for (int i = 1; i <= a0; i+) tmpi = ai * x;int l = a0 + MAX; for (int i = 1; i <= l; i+) if (tmpi > 9) tmpi +

14、 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(b, tmp, sizeof(b); return ;高精度數(shù)除整型取余 在高精度數(shù)除整型中需要兩個高精度數(shù)組，被除數(shù)和商，以及整型rest存儲余數(shù)。如果需要取小數(shù)部分，用余數(shù)除除數(shù)，將每一位的小數(shù)存入數(shù)組即可。void div_int(hp a, int x, hp &res, int &rest) memset(res, 0, sizeof(res); rest = 0; for (int i = a0

15、; i >= 1; i-) rest = rest * 10 + ai; if (rest >= x) resi = rest / x, rest %= x;int l = a0; while (resl = 0 && l > 1) l-; res0 = l; return ;四、高精度數(shù)與高精度數(shù)的運算 以下代碼中a, b為進行運算的兩個高精度數(shù)，c為結(jié)果。高精度數(shù)加高精度數(shù) 同筆算式，對應(yīng)位相加，最后統(tǒng)一進位，也可以邊加進位。（個人覺得統(tǒng)一進位比較好）void add_hp(hp a, hp b, hp &c)hp tmp; memset(tmp,

16、 0, sizeof(tmp);int l = max(a0, b0); for (int i = 1; i <= l; i+) tmpi = ai + bi; l+; for (int i = 1; i <= l; i+) if (tmpi > 9) tmpi + 1+, tmpi -= 10; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ;高精度數(shù)減高精度數(shù) 高精度數(shù)減高精度數(shù)，需要判斷減數(shù)和被減數(shù)的大小關(guān)系，相等時視為被減數(shù)大。用一個布爾類型 Is

17、Pos 來標志結(jié)果的正負。如果被減數(shù)比減數(shù)小則需要交換兩數(shù)。減法的主函數(shù)部分返回值為 IsPos。 比較大小的代碼：bool compare(hp a, hp b) if (a0 > b0) return true; if (a0 < b0) return false; for (int i = a0; i >= 1; i-) if (ai > bi) return true; if (ai < bi) return false; return true; 交換兩數(shù)：void exchange(hp &a, hp &b)hp tmp; memcpy

18、(a, tmp, sizeof(tmp); memcpy(b, a, sizeof(a); memcpy(tmp, b, sizeof(b); return ; 兩數(shù)相減的代碼（運行后若a < b，則a，b會交換）：bool sub_hp(hp &a, hp &b, hp &c)hp tmp;bool IsPos;int l; memset(tmp, 0, sizeof(tmp); IsPos = compare(a, b); if (IsPos = false) exchange(a, b); l = a0; for (int i = 1; i <= l;

19、 i+) tmpi = ai - bi; for (int i = 1; i <= l; i+) if (tmpi < 0) tmpi + 1-, tmpi += 10; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return IsPos;高精度數(shù)乘高精度數(shù) 從兩個數(shù)相乘的筆算式中，個位數(shù)乘上十位數(shù)的積的最末一位是在十位，所十位數(shù)乘上十位數(shù)則是在百位。由此推出對于ai * bj這個結(jié)果應(yīng)該儲存在 ci + j - 1位上。（這個結(jié)論讀者可以自己論證）而高精度乘高精度就是利

20、用了這個性質(zhì)。因為等于某個定值的 i, j組合不一定只有一種，所以要把每一次的積累加起來。 兩個數(shù)相乘其結(jié)果的位數(shù)一定小于或等于兩個數(shù)位數(shù)之和，這一點也請讀者自己證明。void mul_hp(hp a, hp b, hp &c)int l;hp tmp; memset(tmp, 0, sizeof(tmp); for (int i = 1; i <= a0; i+) for (int j = 1; j <= b0; j+) tmpi + j - 1 += ai * bj; l = a0 + b0; for (int i = 1; i <= l; i+) if (tmp

21、i > 9) tmpi + 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ;高精度數(shù)除高精度數(shù)取余 目前就我所知道的，多是用二分商、乘法和減法結(jié)合求解。將可能出現(xiàn)的最大和最小的商進行二分，每次用中間數(shù)乘上除數(shù)，若結(jié)果大于被除數(shù)，將中間數(shù)作為上界繼續(xù)二分；否則用被除數(shù)減去該數(shù)，如果此時結(jié)果小于除數(shù)，即中間數(shù)為商，否則將中間數(shù)作為下界再次二分。 下面的代碼為商為整型時的除法主函數(shù)，返回值為商：int div_hp(h

22、p &a, hp &b, hp &rest)hp tmp;int l = MIN_RES, r = MAX_RES, mid; while (l <= r) mid = (l + r) / 2; mul_int(b, mid, tmp); if (compare(a, tmp) = false) r = mid; else sub_hp(a, tmp, tmp); if (compare(tmp, b) = true) l = mid; else memcpy(rest, tmp, sizeof(tmp); return mid; return 0;五、高精度數(shù)的

23、進制轉(zhuǎn)換 首先需要一個改良版的高精度數(shù)除整型取余，增加一個k參數(shù)表示當前高精度數(shù)的進制。 代碼如下，返回值為余數(shù)：int change_div_int(hp a, int x, hp &res, int k)int rest;hp tmp; memset(tmp, 0, sizeof(tmp); rest = 0; for (int i = a0; i >= 1; i-) rest = rest * k + ai; if (rest >= x) tmpi = rest / x, rest %= x; int l = a0; while (tmpl = 0 &&

24、; l > 1) l-; tmp0 = l; memcpy(res, tmp, sizeof(tmp); return rest; 高精度進制轉(zhuǎn)換的主函數(shù)，n為當前進制，k為目標進制，b為結(jié)果：void N_to_K(hp &a, int n, int k, hp &b) memset(b, 0, sizeof(b); while (a0 != 1 | a1 != 0) b0+; bb0 = change_div_int(a, k, a, n); return ;六、高精度冪運算 冪即指數(shù)，表示一個數(shù)自乘多少次，如55即表示5個5相乘。在介紹高精度冪運算之前，首先介紹一個

25、東西快速冪。快速冪 比如求926時最先想到的方法就是用for循環(huán)乘上26次，若指數(shù)很大，就需要做很多次循環(huán)。對于高精度數(shù)來說做幾十次乘法就已經(jīng)很費時間了，如果指數(shù)上千甚至上萬時必然會TLE。那么應(yīng)該怎么辦呢？我們先從926分析。 926 = 916 * 98 * 92 將上面的各因子的指數(shù)列表出來為：指數(shù)12481632是否含有（1或0）010110 將第二行的數(shù)自右向左寫做一行為 11010，把這個數(shù)作為二進制的話剛好表示的就是26。 根據(jù)這個規(guī)律我們就得出了一個快速求出某個數(shù)冪的方法，即快速冪。將指數(shù)寫成二進制，若該位為1則乘上對應(yīng)的因子。在代碼里會用到位運算的一些知識，這里先說明一下。

26、C+Pascal意義x & 1x and 1x除二后取余。x >> 1x shr 1把x向右移動一位即除以2，取整。 整型快速冪代碼（n為底數(shù)，k為指數(shù)）：int QM(int n, int k)int tmp = n, res = 1; while (k != 0) if (k & 1) res *= tmp; tmp *= tmp; k = k >> 1; return res;高精度數(shù)的快速冪 先將底數(shù)轉(zhuǎn)化為高精度數(shù)，然后只要將上面的整型全部替換為高精度數(shù)即可。代碼如下： 冪為整型：void QM_int(hp a, int k, hp &

27、b)hp tmp, res; memcpy(tmp, a, sizeof(tmp); /復(fù)制底數(shù) memset(res, 0, sizeof(res); /清零 res0 = res1 = 1; while (k != 0) if (k & 1) mul_hp(res, tmp, res); mul_hp(tmp, tmp, tmp); k = k >> 1; memcpy(b, res, sizeof(b); return ; 冪為高精度（十進制）：void QM_int(hp a, hp &k, hp &b)hp tmp, res; memcpy(tmp

28、, a, sizeof(tmp); /復(fù)制底數(shù) memset(res, 0, sizeof(res); /清零 res0 = res1 = 1; while (k0 != 1 | k1 != 0) if (change_div_int(k, 2, k, 10) mul_hp(res, tmp, res); mul_hp(tmp, tmp, tmp); memcpy(b, res, sizeof(b); return ;七、壓位高精度數(shù) 壓位高精度數(shù)，從名字上即可知道，是減少數(shù)組大小的高精度數(shù)。那么要減少數(shù)組大小應(yīng)該怎么做了？答案很簡單，上面的例子中我們一直都使用的十進制，即每一位只表示0到9，

29、對于可以表示十位數(shù)的int而言，顯然的浪費空間，所以我們可以讓它表示0到99（百進制），0到999（千進制）等等。這樣的話既可以節(jié)約內(nèi)存，又可以在一定程度上縮短時間。但是要注意的是，出了最高位以外，其它位上的數(shù)據(jù)如果沒達到位數(shù)，需要補零。比如在千進制中中間某一位為99，則輸出時要多輸出一個0，為099。讀入也需要改變，如讀入32146789787645612則,億進制下，數(shù)組為a|3|87645612|21467897|3| 下面是一個億進制的高精度加法：const int d8 = 1, 10, 100, 1000,10000,100000,1000000,10000000;char str

30、MAXL;void init(hp &a)int l = 0, k = 1; memset(a, 0, sizeof(a); scanf("%s", str); /讀入字符串 while (strl + 1) l+; for (int i = 0; i <= l; i+) ak += (strl - i - '0') * di % 8; if (i % 8 = 7) k+; if (!ak) k-; a0 = k; return ;void add(hp a, hp b, hp &c)int l = max(a0, b0);hp tmp

31、; memset(tmp, 0, sizeof(tmp); for (int i = 1; i <= l; i+) tmpi = ai + bi; for (int i = 1; i <= l; i+) if (tmpi >= 100000000) tmpi + 1 +, tmpi -= 100000000; l+; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ;void prin(hp a)printf(aa0)for (int i = a0 - 1; i >= 1; i-)printf(&qu