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

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

2、 255Word0 65535Longword0 4294967295Qword實(shí)型的精度是指當(dāng)該類型的數(shù)據(jù)位數(shù)超過精度范圍時(shí)自動(dòng)對(duì)超過的部分進(jìn)行四舍五入。比如將存入 real 時(shí)就會(huì)變?yōu)?1.234568E12，后面的890123 被四舍五入，只保留了位數(shù)。實(shí)型范圍精度real2.9E-39 1.7E3811至12single1.5E-45 3.4E387至8double5.0E-324 1.7E30815至16但是在某些計(jì)算中，參與運(yùn)算的數(shù)的范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型（整型，實(shí)型）能表示的范圍的運(yùn)算，例如求兩個(gè)100位數(shù)的和的精確值。如果用一個(gè)整型變量，無論如何也是存儲(chǔ)不了的，用實(shí)型則會(huì)造

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

4、的位數(shù)，而從a1到aa0分別從低位到高位存儲(chǔ)高精度數(shù)的每一位數(shù)（這樣每當(dāng)一位超過9時(shí)，會(huì)向前一進(jìn)位的高精度數(shù)，為十進(jìn)制高精度數(shù)）。未使用的部分均為0。數(shù)組下標(biāo)012345678910111213存儲(chǔ)數(shù)據(jù)1221098765432100高精度數(shù)的讀入 高精度數(shù)一般采用字符串的方式，也可以采用字符的方式（以回車符作為結(jié)束的標(biāo)志）。非讀入型的高精度數(shù)，同常賦值為a0 = a1 = 1 （多用于乘法）或 a0 = 1, a1 = 0（多用于加減）下面為字符串式的讀入（十進(jìn)制）： 字符串，特別說明C+里字符串以下標(biāo)0開始，Pascal以1開始。 C+Pascalvoid Init(hp &a)s

5、tring 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;begin fillchar(a, sizeof(a), 0); /清零 readln(s); l = length(s); for i := l downto 1 do ai :=

6、 ord(sl i + 1) ord('0'); a0 := l;end;高精度進(jìn)位 當(dāng) ai上的數(shù)據(jù)大于等于10的時(shí)候，就要向高位進(jìn)位了。因?yàn)樵摂?shù)組中下標(biāo)越大，位數(shù)越高，故對(duì)ai位進(jìn)行進(jìn)位的操作為： C+Pascalai + 1 = ai / 10;ai + 1 := ai div 10;ai %= 10ai := ai mod 10; 如果aa0位也大于等于10，在進(jìn)位的同時(shí)就要考慮a0的值的改變了。本文的處理方式是先估計(jì)a0能改變的最大值，再依次減小，直到達(dá)到準(zhǔn)確位數(shù)。 C+Pascall = a0 + MAX;while (al = 0 && l >

7、; 1) l-;a0 = l;l := a0 + MAX;while (al = 0 and l > 1) do dec(l);a0 := l; 高精度退位當(dāng) ai上的數(shù)據(jù)小于0的時(shí)候，就要由高位退位了。因?yàn)樵摂?shù)組中下標(biāo)越大，位數(shù)越高，故當(dāng)ai位小于0時(shí)，ai + 1位退位的操作（以十進(jìn)制為例）為： C+Pascalai + 1-;dec(ai + 1);ai += 10ai := ai + 10; 如果aa0位等于0，在退位的同時(shí)就要考慮a0的值的改變了。此時(shí)要減小a0，直到達(dá)到準(zhǔn)確位數(shù)。 C+Pascalwhile (aa0 = 0 && a0 > 1) a0-

8、;while (aa0 = 0 and a0 > 1) do dec(a0); 一般的當(dāng)被減數(shù)小于減數(shù)時(shí)，會(huì)交換兩數(shù)，所以不會(huì)出現(xiàn)結(jié)果為負(fù)數(shù)的情況。高精度數(shù)的輸出 從aa0開始遞減輸出，直到a1: C+Pascalvoid prin(hp a) for (int i = a0; i >= 1; i-) cout << ai; cout << endl;return ;procedure Prin(a: hp)var i: integer;begin for i := a0 downto 1 do write(ai); writeln;end;三、高精度數(shù)與整

9、型的運(yùn)算從這里開始，本文只寫出C+的算法，使用Pascal的OIers若有不懂的地方，可參照前面幾個(gè)對(duì)比的代碼進(jìn)行理解，未出現(xiàn)過的代碼，本文會(huì)注明。以下代碼中a為參與運(yùn)算的高精度數(shù)，b為結(jié)果。高精度數(shù)加整型 高精度數(shù)加整型有兩種算法： 一是將整型加到a1后，再不斷進(jìn)位，直到ai小于10為止。但是如果a1+x就已經(jīng)溢出整型的范圍的話，就需要a1+x%10，a2+x/10后再進(jìn)位。 另一種就是把x的每一位加到對(duì)應(yīng)位上再統(tǒng)一進(jìn)位。 相對(duì)而言第一種方法用的最多，因?yàn)樘厥馇闆r出現(xiàn)的很少。 代碼如下：/第一種void add_int(hp a, int x, hp &b)hp tmp; memcp

10、y(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, hp &b)hp tmp; memcpy(tmp, a, sizeof(tmp);int l = 0; while (x) l+, tmpl += x % 10, x /

11、= 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ù)小于整型，我個(gè)人建議就不用高精度，把高精度轉(zhuǎn)化為整型直接減。這里只討論高精度數(shù)大于整型。 將高精度數(shù)的對(duì)應(yīng)位同x對(duì)應(yīng)位相減，再進(jìn)行退位。void sub_int(hp a, int x, hp

12、&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-;memcpy(b, tmp, sizeof(b);return ;高精度數(shù)乘整型 高精度數(shù)的每一位都乘上x，再逐一進(jìn)位即可。要注意ai * x 不能超過整型范圍。int MAX

13、 = 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 + 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(b,

14、 tmp, sizeof(b); return ;高精度數(shù)除整型取余 在高精度數(shù)除整型中需要兩個(gè)高精度數(shù)組，被除數(shù)和商，以及整型rest存儲(chǔ)余數(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; i >= 1; i-) rest = rest * 10 + ai; if (rest >= x) resi = rest / x, rest %= x;int

15、l = a0; while (resl = 0 && l > 1) l-; res0 = l; return ;四、高精度數(shù)與高精度數(shù)的運(yùn)算 以下代碼中a, b為進(jìn)行運(yùn)算的兩個(gè)高精度數(shù)，c為結(jié)果。高精度數(shù)加高精度數(shù) 同筆算式，對(duì)應(yīng)位相加，最后統(tǒng)一進(jìn)位，也可以邊加進(jìn)位。（個(gè)人覺得統(tǒng)一進(jìn)位比較好）void add_hp(hp a, hp b, hp &c)hp tmp; memset(tmp, 0, sizeof(tmp);int l = max(a0, b0); for (int i = 1; i <= l; i+) tmpi = ai + bi; l+; f

16、or (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í)視為被減數(shù)大。用一個(gè)布爾類型 IsPos 來標(biāo)志結(jié)果的正負(fù)。如果被減數(shù)比減數(shù)小則需要交換兩數(shù)。減法的主函數(shù)部分返回值為 IsPos。 比較大小的代碼：bool compare(hp a, hp b) if (a0

17、 > 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(a, tmp, sizeof(tmp); memcpy(b, a, sizeof(a); memcpy(tmp, b, sizeof(b); return ; 兩數(shù)相減的代碼（

18、運(yùn)行后若a < b，則a，b會(huì)交換）：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; i+) tmpi = ai - bi; for (int i = 1; i <= l; i+) if (tmpi < 0) tmpi + 1-, tmpi += 1

19、0; while (tmpl = 0 && l > 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return IsPos;高精度數(shù)乘高精度數(shù) 從兩個(gè)數(shù)相乘的筆算式中，個(gè)位數(shù)乘上十位數(shù)的積的最末一位是在十位，所十位數(shù)乘上十位數(shù)則是在百位。由此推出對(duì)于ai * bj這個(gè)結(jié)果應(yīng)該儲(chǔ)存在 ci + j - 1位上。（這個(gè)結(jié)論讀者可以自己論證）而高精度乘高精度就是利用了這個(gè)性質(zhì)。因?yàn)榈扔谀硞€(gè)定值的 i, j組合不一定只有一種，所以要把每一次的積累加起來。 兩個(gè)數(shù)相乘其結(jié)果的位數(shù)一定小于或等于兩個(gè)數(shù)位數(shù)之和，這一點(diǎn)也請(qǐng)讀者自己證明。void

20、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 (tmpi > 9) tmpi + 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 && l > 1) l-; tmp

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

22、= 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ù)的進(jìn)制轉(zhuǎn)換 首先需要一個(gè)改良版的高精度數(shù)除整型取余，增加一個(gè)k參數(shù)表示當(dāng)前高精度數(shù)的進(jìn)制。 代碼如下，返回值為余數(shù)：int change_div_int(hp a, int x,

23、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 && l > 1) l-; tmp0 = l; memcpy(res, tmp, sizeof(tmp); return rest; 高精度進(jìn)制轉(zhuǎn)換的主函數(shù)，n為當(dāng)前進(jìn)制，k

24、為目標(biāo)進(jìn)制，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 ;六、高精度冪運(yùn)算 冪即指數(shù)，表示一個(gè)數(shù)自乘多少次，如55即表示5個(gè)5相乘。在介紹高精度冪運(yùn)算之前，首先介紹一個(gè)東西快速冪?？焖賰?比如求926時(shí)最先想到的方法就是用for循環(huán)乘上26次，若指數(shù)很大，就需要做很多次循環(huán)。對(duì)于高精度數(shù)來說做幾十次乘法就已經(jīng)很費(fèi)時(shí)間了，如果指數(shù)上千甚至上萬時(shí)必

25、然會(huì)TLE。那么應(yīng)該怎么辦呢？我們先從926分析。 926 = 916 * 98 * 92 將上面的各因子的指數(shù)列表出來為：指數(shù)12481632是否含有（1或0）010110 將第二行的數(shù)自右向左寫做一行為 11010，把這個(gè)數(shù)作為二進(jìn)制的話剛好表示的就是26。 根據(jù)這個(gè)規(guī)律我們就得出了一個(gè)快速求出某個(gè)數(shù)冪的方法，即快速冪。將指數(shù)寫成二進(jìn)制，若該位為1則乘上對(duì)應(yīng)的因子。在代碼里會(huì)用到位運(yùn)算的一些知識(shí)，這里先說明一下。 C+Pascal意義x & 1x and 1x除二后取余。x >> 1x shr 1把x向右移動(dòng)一位即除以2，取整。 整型快速冪代碼（n為底數(shù)，k為指數(shù)）：i

26、nt 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 &b)hp tmp, res; memcpy(tmp, a, sizeof(tmp); /復(fù)制底數(shù) memset(res, 0, sizeof(res); /清零 res0 = r

27、es1 = 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 ; 冪為高精度（十進(jìn)制）：void QM_int(hp a, hp &k, hp &b)hp tmp, res; memcpy(tmp, a, sizeof(tmp); /復(fù)制底數(shù) memset(res, 0, sizeof(res); /清零 res0 = res1 = 1; while (k0 != 1 |

28、 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)該怎么做了？答案很簡(jiǎn)單，上面的例子中我們一直都使用的十進(jìn)制，即每一位只表示0到9，對(duì)于可以表示十位數(shù)的int而言，顯然的浪費(fèi)空間，所以我們可以讓它表示0到99（百進(jìn)制），0到999（千進(jìn)制）等等。這樣的話既可以節(jié)約內(nèi)存，又可以在一定程度上縮短時(shí)間。但是要注意的

29、是，出了最高位以外，其它位上的數(shù)據(jù)如果沒達(dá)到位數(shù)，需要補(bǔ)零。比如在千進(jìn)制中中間某一位為99，則輸出時(shí)要多輸出一個(gè)0，為099。讀入也需要改變，如讀入則,億進(jìn)制下，數(shù)組為a|3|87645612|21467897|3| 下面是一個(gè)億進(jìn)制的高精度加法：const int d8 = 1, 10, 100, 1000,10000,100000,1000000,10000000;char strMAXL;void init(hp &a)int l = 0, k = 1; memset(a, 0, sizeof(a); scanf("%s", str); /讀入字符串 whil

30、e (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; 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("%08d&q