目录
1. 概述 #
高精度数的概念 #
整数和小数有计算精度的限制。比如：
- unsigned long long 的最大值： 1844 6744 0737 0955 1615 （一千八百多万亿）
- long double 的范围： 1.18973e+4932 ~ 3.3621e-4932
太大的数，或者小数点太多的数，在计算上有限制。就需要使用特殊的处理方法。这就称为高精度计算。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。
数据的接收和存贮 #
- 当输入的数很长时，可采用字符串方式输入。
这样可以输入位数很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。
因为数组存放的元素顺序与我们计算的顺序是相反的，在竖式计算中我们是将其右对齐（个位对个位，十位对十位，以此类推），而读取数字后的两个数组是左对齐的，因此我们要将里面的元素逆置。
请读入下面的数：
123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789
示例程序：
void init()
{
string s;
cin >> s; // 读入字符串
len = s.length();
for(i=0; i <= len; ++i) //逆置元素
a[i]=s[len-1] - '0'; // 将字符转化成数字
}
高精度数位数的确定 #
- 方法：接收时往往是用字符串，所以它的位数就等于字符串的长度。
进位，错位处理 #
下面例程中的 a b c 均为整形数组。
- 加法进位：
c[i] = a[i]+b[i];
if(c[i] >= 10)
{
c[i] %= 10;
++c[i+1];
}
- 减法借位：
if(a[i] < b[i])
{
--a[i+1];
a[i]+=10;
}
c[i] = a[i]-b[i];
2. 高精度加法 #
请输入两个数，计算它们的和。
【算法分析】
竖式方法举例：962+93
【例程】
#include < iostream >
#include < string >
using namespace std;
//高精度加法函数
void add(int a[], int a_len, int b[], int b_len, int* result, int& result_len)
{
int i = 0, x = 0;
result_len = 0;
int max_a_b = a_len > b_len ? a_len : b_len;
while (i< max_a_b)
{
int sub_a = i < a_len ? a[i] : 0; //判断i是否超过数组a的长度，若超过该位为0
int sub_b = i < b_len ? b[i] : 0; //判断i是否超过数组b的长度，若超过该位为0
result[i] = sub_a + sub_b + x;//逐位相加
x = result[i] / 10;
result[i] %= 10;
result_len++;
i++;
}
if (x != 0)
{
result[i] = x;
++result_len;
}
}
int main()
{
string astr, bstr;
cin >> astr;
cin >> bstr;
int lena = astr.size(), lenb = bstr.size();
int a[100], b[100];
for (int i = 0; i< lena; ++i)
a[lena - i - 1] = astr[i] - '0'; // 将数字倒过来，并转化成数字
for (int i = 0; i< lenb; ++i)
b[lenb - i - 1] = bstr[i] - '0';
int c[100] = { 0 }, lenc=0;
add(a, lena, b, lenb, c, lenc); // 计算
for (int i = 0; i < lenc; ++i)
{
cout << c[lenc - i - 1]; // 再将数字倒过来输出
}
cout << endl;
return 0;
}
3. 高精度乘法 #
进位和错位处理：高精度✖️单精度 #
先考虑一个简单的情况：乘数中的一个是普通的 int 类型。有没有简单的处理方法呢？
一个直观的思路是直接将a每一位上的数字乘以b。从数值上来说，这个方法是正确的，但它并不符合十进制表示法，因此需要将它重新整理成正常的样子。
重整的方式，也是从个位开始逐位向上处理进位。但是这里的进位可能非常大，甚至远大于9，因为每一位被乘上之后都可能达到9b的数量级。所以这里的进位不能再简单地进行-10运算，而是要通过除以10的商以及余数计算。详见代码注释，也可以参考下图展示的一个计算高精度数1337乘以单精度数42的过程。
当然，也是出于这个原因，这个方法需要特别关注乘数b的范围。若它和 10^9（或相应整型的取值上界）属于同一数量级，那么需要慎用高精度—单精度乘法。
void mul_short(int a[], int b, int c[]) {
clear(c);
for (int i = 0; i < LEN - 1; ++i) {
// 直接把 a 的第 i 位数码乘以乘数，加入结果
c[i] += a[i] * b;
if (c[i] >= 10) {
// 处理进位
// c[i] / 10 即除法的商数成为进位的增量值
c[i + 1] += c[i] / 10;
// 而 c[i] % 10 即除法的余数成为在当前位留下的值
c[i] %= 10;
}
}
}
进位和错位处理：高精度✖️高精度 #
如果两个乘数都是高精度，那么竖式乘法又可以大显身手。
于是可以将b分解为它的所有数码，其中每个数码都是单精度数，将它们分别与a相乘，再向左移动到各自的位置上相加即得答案。当然，最后也需要用与上例相同的方式处理进位。
注意这个过程与竖式乘法不尽相同，我们的算法在每一步乘的过程中并不进位，而是将所有的结果保留在对应的位置上，到最后再统一处理进位，但这不会影响结果。
void mul(int a[], int b[], int c[]) {
clear(c);
for (int i = 0; i < LEN - 1; ++i) {
// 这里直接计算结果中的从低到高第 i 位，且一并处理了进位
// 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
// 这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];
if (c[i] >= 10) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
}
}
高精度乘法实现 #
请输入两个数，计算它们的积。
【算法分析】
竖式方法举例：
- 25*836
int b[] = {2,5};
int a[] = {8,3,6};
b1 b0
___x_____a2_a1_a0__
c2 c1 c0
d2 d1 d0
___e2_e1_e0________
f5 f4 f3 f2 f1 f0
我们不妨改一下数据的下标，以便于更好的理解下面的代码。
b1 b0
___x_____a2_a1_a0__
c2 c1 c0
d3 d2 d1
___e4_e3_e2________
f5 f4 f3 f2 f1 f0
## 1
fi 的计算过程推导，是代码实现的关键。
1. f的序号和ab有什么关系？为什么是【f序号 = a序号 + b序号】
2. fi的值，是一个累加过程。
## 2
两数乘积的位数，如何确定？
f5 可能没有吗？
【例程】
#include < iostream >
#include < string >
using namespace std;
void multiply(int a[], int b[], int a_len, int b_len, int* f, int& f_len)
{
int i = 0, x = 0;
f_len = 0;
for (int i = 0; i < a_len; ++i)
{
int x = 0; // x 表示进位
for (int j = 0; j < b_len; ++j)
{
// 乘法核心代码
f[i+j] += a[i] * b[j] + x;
x = f[i+j] / 10;
f[i+j] %= 10;
}
f[i + b_len] = x;
}
// 根据最后一位是否为 0 ，判断计算结果的位数
if (f[a_len + b_len - 1] == 0)
f_len = a_len + b_len - 1;
else
f_len = a_len + b_len;
}
int main()
{
// 从屏幕获得输入
string astr, bstr;
cin >> astr;
cin >> bstr;
int lena = astr.size(), lenb = bstr.size();
int a[100] = { 0 }, b[100] = { 0 }; // 假设数字的位数不超过 100
for (int i = 0; i < lena; ++i)
a[lena - i - 1] = astr[i] - '0'; // 将数字倒过来
for (int i = 0; i < lenb; ++i)
b[lenb - i - 1] = bstr[i] - '0';
// 计算高精度乘法
int f[100] = { 0 }, lenf(0);
multiply(a, b, lena, lenb, f, lenf); // 必须是两个非负数，且 a 大于 b
// 输出结果
for (int i = 0; i < lenf; ++i)
{
cout << f[lenf - i - 1];
}
cout << endl;
return 0;
}
4. 高精度除法 #
高精度除以低精度 #
假设 a 是一个高精度整数，b是一个普通的整数。
【算法分析】
在高精度除以单精度时，从高位到低位逐位相除。最需要注意的问题是，后一位继承前一位的余数问题。
设高精度的数位数字为a[i]，单精度数为b，第i+1位除b后的余数位r，把r加到i位时，应乘以进制X，即s=X*r+a[i].
- 注意位移处理即可
int b = 5;
int a[] = {8,3,6};
(1)
_1___
5)836
_5___
3
(2)
_16__
5)836
_5___
33
_30__
3
(3)
_167__
5)836
_5___
33
_30__
36
__35_
1
【例程】
#include < iostream >
#include < string >
using namespace std;
void assign(int a[], int a_len, int* dst, int& dst_len)
{
for (int i = 0; i < a_len; ++i)
dst[i] = a[i];
dst_len = a_len;
}
void divide(int a[], int a_len, int b, int* result, int& result_len)
{
int c[100] = { 0 }, lenc = 0; // c 用于存放临时的计算结果
if (a[0] == 0)
{
result_len = 1;
assign(c, 1, result, result_len);
return; // 0是被除数，则商为0
}
int i = 0, x = 0;
result_len = 0;
for (int i = 0; i < a_len; ++i)
{
c[i] = (x * 10 + a[i]) / b;
x = (x * 10 + a[i]) % b;
++lenc;
}
// 去除前部可能出现的 0
int c_startID = 0;
for (; c_startID < 100; ++c_startID)
if (c[c_startID] != 0)
break;
for (int i = c_startID; i < lenc; ++i)
{
result[i - c_startID] = c[i];
++result_len;
}
}
int main()
{
// 从屏幕获得输入 被除数a和除数b均以字符串的形式输入
string astr, bstr;
cin >> astr;
cin >> bstr;
//获得字符串a和b的长度也就是，a和b的位数
int lena = astr.size(), lenb = bstr.size();
//设置数组a[100]高精度数字a
int a[100] = { 0 }, b = 0;
for (int i = 0; i < lena; ++i)
a[i] = astr[i] - '0'; // 除法不需要将数字倒过来
for (int i = 0; i < lenb; ++i)
b += (bstr[i] - '0') * pow(10, lenb - i - 1); // 字符串转 10 进制数
//不能除以0
if (b == 0)
return -1;
// 设置数组c[100]存储计算结果，c[100]中存储的也是高精度的数字
int c[100] = { 0 }, lenc(0);
divide(a, lena, b, c, lenc); // a 是被除数，是高精度值。b是低精度值，用 int 即可存储
// 输出
for (int i = 0; i < lenc; ++i)
{
cout << c[i]; // 正向输出
}
cout << endl;
return 0;
}
高精度除以高精度 #
假设 a 是一个高精度整数，b 也是一个高精度整数。
【算法分析】
- 方法：使用减法模拟除法
将被除数，不断减去除数，直到余数小于除数。
- 1. 需要用到高精度减法
- 2. 需要用到高精度比较大小
- 3. 需要用到高精度加法
【例程】
#include < iostream >
#include < string >
using namespace std;
int zero[] = { 0 };
int one[] = { 1 };
//赋值过程，将数组a[]中的数据赋值给b[],并将a的长度a_len赋值给b_len
void assign(int a[], int a_len, int* b, int& b_len)
{
for (int i=0; i < a_len; ++i)
b[i] = a[i];
b_len = a_len;
}
//高精度加法计算函数
void add(int a[], int a_len, int b[], int b_len, int* result, int& result_len)
{
int i = 0, x = 0;
result_len = 0;
int max_a_b = a_len > b_len ? a_len : b_len;
while (i< max_a_b)
{
int sub_a = i < a_len ? a[i] : 0;
int sub_b = i < b_len ? b[i] : 0;
result[i] = sub_a + sub_b + x;
x = result[i] / 10;
result[i] %= 10;
result_len++;
i++;
}
if (x != 0)
{
result[i] = x;
++result_len;
}
}
//高精度减法计算函数
void jianfa(int a[], int a_len, int b[], int b_len, int* result, int& result_len)
{
int i = 0, x = 0;
result_len = 0;
int max_a_b = a_len > b_len ? a_len : b_len;
while (i < max_a_b)
{
int sub_a = i < a_len ? a[i] : 0;
int sub_b = i < b_len ? b[i] : 0;
// 减法
if (sub_a < sub_b)
{
--a[i + 1];
sub_a += 10;
}
result[i] = sub_a - sub_b;
result_len++;
i++;
}
if (x != 0)
{
result[i] = x;
++result_len;
}
// 假如结果全都是0，输出一个0
int sum(0);
for (int i = 0; i < result_len; ++i)
{
sum += result[i];
if (sum != 0)
break;
}
if (sum == 0)
result_len = 1;
}
// 如果 a==b 返回 0; 如果 a > b, 返回 1; 如果 a < b, 返回 -1;
int compare_a_b(int a[], int a_len, int b[], int b_len)
{
if (a_len > b_len)
return 1;
else if (a_len < b_len)
return -1;
else
{
for (int i= a_len-1; i>=0; --i) // 加减的结果，是倒过来的，所以这里的比较也要倒着比较
{
if (a[i] > b[i])
return 1;
else if (a[i] < b[i])
return -1;
else
continue;
}
}
return 0; // 相等
}
void divide(int a[], int a_len, int b[], int b_len, int* shang, int& shang_len, int* yushu, int& yushu_len)
{
if (0 == compare_a_b(zero, 1, a, a_len))
{
shang_len = 1;
yushu_len = 1;
return; // 0是被除数，则商为0
}
for (;;)
{
jianfa(a, a_len, b, b_len, a, a_len); // 相当于 a -= b;
add(shang, shang_len, one, 1, shang, shang_len);
assign(a, a_len, yushu, yushu_len);// 将最终减法剩余的结果，赋值给余数
if (-1 == compare_a_b(a, a_len, b, b_len)) //
break; // 当余数a小于除数b的时候，退出循环。
}
}
int main()
{
// 从屏幕获得输入
string astr, bstr;
cin >> astr;
cin >> bstr;
int lena = astr.size(), lenb = bstr.size();
int a[100] = { 0 }, b[100] = { 0 };
for (int i = 0; i< lena; ++i)
a[lena - i - 1] = astr[i] - '0'; // 将数字倒过来
for (int i = 0; i< lenb; ++i)
b[lenb - i - 1] = bstr[i] - '0';
if (0 == compare_a_b(zero, 1, b, lenb))
return -1; // 被除数不能是 0
// 计算除法
int shang[100] = { 0 }, yushu[100] = { 0 }, shang_len(0), yushu_len(0);
divide(a, lena, b, lenb, shang, shang_len, yushu, yushu_len); // a 是被除数，是高精度值。b是低精度值，用 int 即可存储
// 输出
cout << "商:";
for (int i=0; i < shang_len; ++i)
cout << shang[shang_len - i - 1]; // 再将数字倒过来输出
cout << endl;
cout << "余数:";
for (int i = 0; i < yushu_len; ++i)
cout << yushu[yushu_len - i - 1]; // 再将数字倒过来输出
cout << endl;
return 0;
}
