数组型高精度数详解

数组型高精度数详解

By Nettle

一、高精度简介

二、高精度数

三、高精度数与整型的运算

四、高精度数与高精度数的运算

五、高精度数的进制转换

六、高精度幂运算

七、压位高精度数

一、高精度简介

首先要知道在计算机里面每一种数据类型都有自己的存储量。由于存储量的限制所以都有着各自的精度，下面是一些常用数据类型的精度：

以Pascal为例

整型的精度就是在该类型范围内所有的数。

整型范围

Shortint-128 (127)

Integer-32768 (32767)

Longint-2147483648 (2147483647)

Int64-9223372036854775808 (9223372036854775807)

Byte0 (255)

Word0 (65535)

Longword0 (4294967295)

Qword0 (18446744073709551615)

实型的精度是指当该类型的数据位数超过精度范围时自动对超过的部分进行四舍五入。比如将1234567890123 存入 real 时就会变为 1.234568E12，后面的890123 被四舍五入，只保留了位数。

实型范围精度

real 2.9E-39 … 1.7E3811至12

single 1.5E-45 … 3.4E387至8

double 5.0E-324 … 1.7E30815至16

但是在某些计算中，参与运算的数的范围大大超出了标准数据类型（整型，实型）能表示的范围的运算，例如求两个100位数的和的精确值。如果用一个整型变量，无论如何也是存储不了的，用实型则会造成数据的不精确。

于是，我们想到了办法，将这个数字拆开，拆成一位一位的或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样表示的数字就被称为高精度数。

对于高精度数，也要像平常数一样做加减乘除以及乘方的运算，于是就有了高精度算法。

二、高精度数

[高精度数的定义]

高精度数事实上就是一个整型数组，根据题目中用的数据的位数设定数组的大小。为了方便通常将高精度数创建为一个新类型，如下：

此时hp a或 a: hp就表示a为hp类型即大小为250的int数组。

在本文中a[0]将存储高精度数的位数，而从a[1]到a[a[0]]分别从低位到高位存储高精度数的每一位数（这样每当一位超过9时，会向前一进位的高精度数，为十进制高精度数）。未使用的部分均为0。

例如将123456789012存入a中为

则a表示一个12位数，从右至左分别为210987654321。

[高精度数的读入]

高精度数一般采用字符串的方式，也可以采用字符的方式（以回车符作为结束的标志）。非读入型的高精度数，同常赋值为a[0] = a[1] = 1 （多用于乘法）或 a[0] = 1, a[1] = 0（多用于加减）下面为字符串式的读入（十进制）：

字符串，特别说明C++里字符串以下标0开始，Pascal以1开始。

[高精度进位]

当 a[i]上的数据大于等于10的时候，就要向高位进位了。因为该数组中下标越大，位数越高，故对a[i]位进行进位的操作为：

如果a[a[0]]位也大于等于10，在进位的同时就要考虑a[0]的值的改变了。本文的处理方式是先估计a[0]能改变的最大值，再依次减小，直到达到准确位数。

[高精度退位]

当 a[i]上的数据小于0的时候，就要由高位退位了。因为该数组中下标越大，位数越高，故当a[i]位小于0时，a[i + 1]位退位的操作（以十进制为例）为：

如果a[a[0]]位等于0，在退位的同时就要考虑a[0]

的值的改变了。此时要减小a[0]，直到达到准确位数。

[高精度数的输出]

从a[a[0]]开始递减输出，直到a[1]:

三、高精度数与整型的运算

从这里开始，本文只写出C++的算法，使用Pascal的OIers若有不懂的地方，可参照前面几个对比的代码进行理解，未出现过的代码，本文会注明。以下代码中a为参与运算的高精度数，b为结果。

[高精度数加整型]

高精度数加整型有两种算法：

一是将整型加到a[1]后，再不断进位，直到a[i]小于10为止。但是如果a[1]+x就已经溢出整型的范围的话，就需要a[1]+x%10，a[2]+x/10后再进位。

另一种就是把x的每一位加到对应位上再统一进位。

相对而言第一种方法用的最多，因为特殊情况出现的很少。

代码如下：

[高精度数减整型]

高精度数减整型，若高精度数小于整型，我个人建议就不用高精度，把高精度转化为整型直接减。这里只讨论高精度数大于整型。

将高精度数的对应位同x对应位相减，再进行退位。

[高精度数乘整型]

高精度数的每一位都乘上x，再逐一进位即可。要注意a[i] * x 不能超过整型范围。

[高精度数除整型取余]

在高精度数除整型中需要两个高精度数组，被除数和商，以及整型rest存储余数。如果需要取小数部分，用余数除除数，将每一位的小数存入数组即可。

四、高精度数与高精度数的运算

以下代码中a, b为进行运算的两个高精度数，c为结果。

[高精度数加高精度数]

同笔算式，对应位相加，最后统一进位，也可以边加进位。（个人觉得统一进位比较好）

[高精度数减高精度数]

高精度数减高精度数，需要判断减数和被减数的大小关系，相等时视为被减数大。用一个布尔类型 IsPos 来标志结果的正负。如果被减数比减数小则需要交换两数。减法的主函数部分返回值为 IsPos。

比较大小的代码：

交换两数：

两数相减的代码（运行后若a < b，则a，b会交换）：

[高精度数乘高精度数]

从两个数相乘的笔算式中，个位数乘上十位数的积的最末一位是在十位，所十位数乘上十位数则是在百位。由此推出对于a[i] * b[j]这个结果应该储存在 c[i + j - 1]位上。（这个结论读者可以自己论证）而高精度乘高精度就是利用了这个性质。因为等于某个定值的 i, j组合不一定只有一种，所以要把每一次的积累加起来。

两个数相乘其结果的位数一定小于或等于两个数位数之和，这一点也请读者自己证明。

[高精度数除高精度数取余]

目前就我所知道的，多是用二分商、乘法和减法结合求解。将可能出现的最大和最小的商进行二分，每次用中间数乘上除数，若结果大于被除数，将中间数作为上界继续二分；否则用被除数减去该数，如果此时结果小于除数，即中间数为商，否则将中间数作为下界再次二分。

下面的代码为商为整型时的除法主函数，返回值为商：

五、高精度数的进制转换

首先需要一个改良版的高精度数除整型取余，增加一个k参数表示当前高精度数的进制。

代码如下，返回值为余数：

高精度进制转换的主函数，n为当前进制，k为目标进制，b为结果：

六、高精度幂运算

幂即指数，表示一个数自乘多少次，如5^5即表示5个5相乘。

在介绍高精度幂运算之前，首先介绍一个东西——快速幂。

[快速幂]

比如求9^26时最先想到的方法就是用for循环乘上26次，若指数很大，就需要做很多次循环。对于高精度数来说做几十次乘法就已经很费时间了，如果指数上千甚至上万时必然会TLE。那么应该怎么办呢？我们先从9^26分析。

9^26 = 9^16 * 9^8 * 9^2

将上面的各因子的指数列表出来为：