High Precision
本文介绍了高精度算法的相关内容。
引言
在 c++中提供了运算符和数据类型来支持我们做运算。
cout << 3 + 5 << endl;但是 c++中的数据类型在定义时就有固定大小的空间。 如 int 为 4 字节 32 为，最大表示范围为
cout << INT32_MAX << endl;
2147483647高精度算法主要处理以下四类问题
- A + B
- A - B
- A * n
- A / n
其中 A , B 的位数 <= 10^6 , n <= 10000
读入和存储
字符串的读入没有长度限制，这里首先读入字符串，再存入向量。
[注: 向量支持动态扩容，相比数组有更好的空间性能]
string a , b;
vector<int> A , B;
cin >> a >> b; // 字符串的读入没有长度限制
for(int i = a.size() - 1 ; i >= 0 ; i--) A.push_back(a[i] - '0');
for(int i = b.size() - 1 ; i >= 0 ; i--) B.push_back(b[i] - '0');另外在数组中采用小端存储的方式，即表现为倒着存储。如读入 123 ，则向量中为
这是因为如果运算产生进位，那么把它直接加在尾部比较容易。
A + B 问题
vector<int> add(vector<int>& A , vector<int>& B)
{
vector<int> R;
int t = 0;
// 在每一轮开始前 t都是前一位运算结果的进位
for(int i = 0 ; i < A.size() || i < B.size() ; i++)
{
if(i < A.size()) t += A[i];
if(i < B.size()) t += B[i];
R.push_back(t % 10); // 将当前位运算结果模10加入结果中
t /= 10; // 产生下一位的进位
}
if(t) R.push_back(1); // 如果最后还有进位 加到结果中
return R;
}A - B 问题
在完成 A - B 问题时 需要先设计一个函数来比较两数的大小 减法算法只处理较大的数减掉较小的数
- 首先比较数的位数 位数长的数大
- 位数一样的情况下 从高位(向量的高端)开始逐位比较 位数字大的数大
- 相等 返回 true
bool cmp(vector<int>& A, vector<int>& B)
{
// 首先比较长度
if(A.size() != B.size()) return A.size() > B.size();
for(int i = A.size() - 1 ; i >= 0 ; i--)
{
if(A[i] == B[i]) // 如果两位相等 继续比较下一位
continue;
return A[i] > B[i]; // 返回当前位大的数
}
return true;
}接着做减法 向加法一样合理处理进位即可
vector<int> sub(vector<int>& A , vector<int>& B)
{
vector<int> R;
// A >= B
for(int i = 0 , t = 0 ; i < A.size() ; i++)
{
// 在循环开始时 t代表上一位的进位 这形成了当前一步的被减数
t = A[i] - t;
// 由于 A >= B 所以要保证减法时 i 对于B不溢出 B[i] 是当前一步的减数
if(i < B.size()) t -= B[i];
// 把相减的结果存入R 如果自然减去后小于零 那么向前借10
R.push_back((t+10)%10);
// 根据是否小于零产生下一步的进位
if(t < 0) t = 1;
else t = 0;
}
// 去掉多余的零 123 - 120 = 003
while(R.size() > 1 && R.back() == 0)
R.pop_back();
return R;
}【注: 在输出结果时，如果小数减去大数，则加上负号。 】
A * n 问题
在高精度乘法 我们处理的问题是 一个大数 A 乘 一个一般数 n(可以存入 int)
这里我们使用的思想是将 n 视为一个数 每次将它和 A 的一位相乘 位相乘结果的低位作为结果 高位作为进位
vector<int> mul(vector<int>& A , int b)
{
vector<int> R;
int t = 0;
for(int i = 0 ; i < A.size() || t; i ++)
{
// 大数没有乘完 或者存在进位t
if(i < A.size())t += A[i] * b;
// 位乘法结果的低一位作为该位的结果
R.push_back(t % 10);
// 高位全部作为进位
t /= 10;
}
return R;
}A / n 问题
该问题的 A 和 n 的性质同 A * n。
在除法中，我们需要得到商和余数。
// 商为R 余数为r
vector<int> div(vector<int>& A , int b , int& r)
{
vector<int> R;
r = 0;
for(int i = A.size() - 1 ; i >= 0 ; i--)
{
r = r * 10 + A[i]; // 和乘法相反 高位留下的数在下一次运算时要乘以10
R.push_back(r / b); // 结果加上当前位运算的结果 如果不够则直接上0
r %= b; // 被除数取模
}
reverse(R.begin(), R.end()); // 因为得到的结果 先存储高位再存储低位 这和默认的存储规则相反
while(R.size() > 1 && R.back() == 0) R.pop_back(); // 去掉高位多余的零
return R;
}版权所有
版权归属：