数组型高精度数详解.doc

数组型高精度数详解 By Nettle 2009-9-9数组型高精度数详解By Nettle一、高精度简介二、高精度数三、高精度数与整型的运算四、高精度数与高精度数的运算五、高精度数的进制转换六、高精度幂运算七、压位高精度数一、高精度简介 首先要知道在计算机里面每一种数据类型都有自己的存储量。由于存储量的限制所以都有着各自的精度，下面是一些常用数据类型的精度：以Pascal为例 整型的精度就是在该类型范围内所有的数。整型范围Shortint-128 127Integer-32768 32767Longint-2147483648 2147483647Int64-9223372036854775808 9223372036854775807Byte0 255Word0 65535Longword0 4294967295Qword0 18446744073709551615实型的精度是指当该类型的数据位数超过精度范围时自动对超过的部分进行四舍五入。比如将 1234567890123 存入 real 时就会变为 1.234568E12，后面的890123 被四舍五入，只保留了位数。实型范围精度real2.9E-39 1.7E3811至12single1.5E-45 3.4E387至8double5.0E-324 1.7E30815至16但是在某些计算中，参与运算的数的范围大大超出了标准数据类型（整型，实型）能表示的范围的运算，例如求两个100位数的和的精确值。如果用一个整型变量，无论如何也是存储不了的，用实型则会造成数据的不精确。于是，我们想到了办法，将这个数字拆开，拆成一位一位的或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样表示的数字就被称为高精度数。对于高精度数，也要像平常数一样做加减乘除以及乘方的运算，于是就有了高精度算法。二、高精度数高精度数的定义 高精度数事实上就是一个整型数组，根据题目中用的数据的位数设定数组的大小。为了方便通常将高精度数创建为一个新类型，如下：C+Pascaltypedef int hp250;type hp = array 0.250 of integer;此时hp a或 a: hp就表示a为hp类型即大小为250的int数组。在本文中a0将存储高精度数的位数，而从a1到aa0分别从低位到高位存储高精度数的每一位数（这样每当一位超过9时，会向前一进位的高精度数，为十进制高精度数）。未使用的部分均为0。例如将123456789012存入a中为数组下标012345678910111213存储数据1221098765432100则a表示一个12位数，从右至左分别为210987654321。高精度数的读入 高精度数一般采用字符串的方式，也可以采用字符的方式（以回车符作为结束的标志）。非读入型的高精度数，同常赋值为a0 = a1 = 1 （多用于乘法）或 a0 = 1, a1 = 0（多用于加减）下面为字符串式的读入（十进制）： 字符串，特别说明C+里字符串以下标0开始，Pascal以1开始。 C+Pascalvoid Init(hp &a)string s;int l; memset(a, 0, sizeof(a); /清零 cin s; l = s.size(); /得到数的位数 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 := ord(sl i + 1) ord(0); a0 := l;end;高精度进位 当 ai上的数据大于等于10的时候，就要向高位进位了。因为该数组中下标越大，位数越高，故对ai位进行进位的操作为： C+Pascalai + 1 = ai / 10;ai + 1 := ai div 10;ai %= 10ai := ai mod 10; 如果aa0位也大于等于10，在进位的同时就要考虑a0的值的改变了。本文的处理方式是先估计a0能改变的最大值，再依次减小，直到达到准确位数。 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上的数据小于0的时候，就要由高位退位了。因为该数组中下标越大，位数越高，故当ai位小于0时，ai + 1位退位的操作（以十进制为例）为： C+Pascalai + 1-;dec(ai + 1);ai += 10ai := ai + 10; 如果aa0位等于0，在退位的同时就要考虑a0的值的改变了。此时要减小a0，直到达到准确位数。 C+Pascalwhile (aa0 = 0 & a0 1) a0-;while (aa0 = 0 and a0 1) do dec(a0); 一般的当被减数小于减数时，会交换两数，所以不会出现结果为负数的情况。高精度数的输出 从aa0开始递减输出，直到a1: C+Pascalvoid prin(hp a) for (int i = a0; i = 1; i-) cout ai; cout 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 /= 10; l = max(tmp0, l); for (int i = 1; i 9) tmpi + 1+, tmpi -=10; l+; while (tmpl = 0 & l 1) l-; tmp0 = l;memcpy(b, tmp, sizeof(b); return ;高精度数减整型 高精度数减整型，若高精度数小于整型，我个人建议就不用高精度，把高精度转化为整型直接减。这里只讨论高精度数大于整型。 将高精度数的对应位同x对应位相减，再进行退位。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 1) tmp0-;memcpy(b, tmp, sizeof(b);return ;高精度数乘整型 高精度数的每一位都乘上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 9) tmpi + 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 & l 1) l-; tmp0 = l; memcpy(b, tmp, sizeof(b); return ;高精度数除整型取余 在高精度数除整型中需要两个高精度数组，被除数和商，以及整型rest存储余数。如果需要取小数部分，用余数除除数，将每一位的小数存入数组即可。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 l = a0; while (resl = 0 & l 1) l-; res0 = l; return ;四、高精度数与高精度数的运算 以下代码中a, b为进行运算的两个高精度数，c为结果。高精度数加高精度数 同笔算式，对应位相加，最后统一进位，也可以边加进位。（个人觉得统一进位比较好）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+; for (int i = 1; i 9) tmpi + 1+, tmpi -= 10; while (tmpl = 0 & l 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ;高精度数减高精度数 高精度数减高精度数，需要判断减数和被减数的大小关系，相等时视为被减数大。用一个布尔类型 IsPos 来标志结果的正负。如果被减数比减数小则需要交换两数。减法的主函数部分返回值为 IsPos。 比较大小的代码：bool compare(hp a, hp b) if (a0 b0) return true; if (a0 = 1; i-) if (ai bi) return true; if (ai bi) return false; return true; 交换两数：void exchange(hp &a, hp &b)hp tmp; memcpy(a, tmp, sizeof(tmp); memcpy(b, a, sizeof(a); memcpy(tmp, b, sizeof(b); return ; 两数相减的代码（运行后若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; i+) tmpi = ai - bi; for (int i = 1; i = l; i+) if (tmpi 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return IsPos;高精度数乘高精度数 从两个数相乘的笔算式中，个位数乘上十位数的积的最末一位是在十位，所十位数乘上十位数则是在百位。由此推出对于ai * bj这个结果应该储存在 ci + j - 1位上。（这个结论读者可以自己论证）而高精度乘高精度就是利用了这个性质。因为等于某个定值的 i, j组合不一定只有一种，所以要把每一次的积累加起来。 两个数相乘其结果的位数一定小于或等于两个数位数之和，这一点也请读者自己证明。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 9) tmpi + 1 += tmpi / 10, tmpi %= 10; while (tmpl = 0 & l 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ;高精度数除高精度数取余 目前就我所知道的，多是用二分商、乘法和减法结合求解。将可能出现的最大和最小的商进行二分，每次用中间数乘上除数，若结果大于被除数，将中间数作为上界继续二分；否则用被除数减去该数，如果此时结果小于除数，即中间数为商，否则将中间数作为下界再次二分。 下面的代码为商为整型时的除法主函数，返回值为商：int div_hp(hp &a, hp &b, hp &rest)hp tmp;int l = MIN_RES, r = MAX_RES, mid; while (l = 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; 高精度进制转换的主函数，n为当前进制，k为目标进制，b为结果：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 ;六、高精度幂运算 幂即指数，表示一个数自乘多少次，如55即表示5个5相乘。在介绍高精度幂运算之前，首先介绍一个东西快速幂。快速幂 比如求926时最先想到的方法就是用for循环乘上26次，若指数很大，就需要做很多次循环。对于高精度数来说做几十次乘法就已经很费时间了，如果指数上千甚至上万时必然会TLE。那么应该怎么办呢？我们先从926分析。 926 = 916 * 98 * 92 将上面的各因子的指数列表出来为：指数12481632是否含有（1或0）010110 将第二行的数自右向左写做一行为 11010，把这个数作为二进制的话刚好表示的就是26。 根据这个规律我们就得出了一个快速求出某个数幂的方法，即快速幂。将指数写成二进制，若该位为1则乘上对应的因子。在代码里会用到位运算的一些知识，这里先说明一下。 C+Pascal意义x & 1x and 1x除二后取余。x 1x shr 1把x向右移动一位即除以2，取整。 整型快速幂代码（n为底数，k为指数）：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;高精度数的快速幂 先将底数转化为高精度数，然后只要将上面的整型全部替换为高精度数即可。代码如下： 幂为整型：void QM_int(hp a, int k, hp &b)hp tmp, res; memcpy(tmp, a, sizeof(tmp); /复制底数 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, a, sizeof(tmp); /复制底数 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 ;七、压位高精度数 压位高精度数，从名字上即可知道，是减少数组大小的高精度数。那么要减少数组大小应该怎么做了？答案很简单，上面的例子中我们一直都使用的十进制，即每一位只表示0到9，对于可以表示十位数的int而言，显然的浪费空间，所以我们可以让它表示0到99（百进制），0到999（千进制）等等。这样的话既可以节约内存，又可以在一定程度上缩短时间。但是要注意的是，出了最高位以外，其它位上的数据如果没达到位数，需要补零。比如在千进制中中间某一位为99，则输出时要多输出一个0，为099。读入也需要改变，如读入32146789787645612则,亿进制下，数组为a|3|87645612|21467897|3| 下面是一个亿进制的高精度加法：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); /读入字符串 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; memset(tmp, 0, sizeof(tmp); for (int i = 1; i = l; i+) tmpi = ai + bi; for (int i = 1; i = 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