大数运算：高精度算法实现与应用
这属于数值计算领域的重要技术
实现高精度算法是一项挑战性较高的任务，但在处理超长数字运算时不可或缺。 虽然在实际编程中不常使用，但在特定场景下，高精度算法是唯一可行的解决方案。
在标准C++中，int类型最多表示9位数字，long long类型约为18位，即使是__int128也只能处理30多位数字。 然而，当需要处理数百甚至上千位的数字时，就必须采用高精度算法。 其核心原理是将数字以字符串形式存储，并通过字符串模拟加减乘除运算过程。 随着技术发展，现在通常使用vector容器来存储大整数。
值得注意的是，高精度算法有一种优化方法称为压位。常规做法是每个int只存储1位数字，但这非常浪费空间。由于int可以存储最多9位数字，我们可以让每个int存储9位数字，从而减少时间和空间复杂度。通常采用8位压位而非9位，以防止意外溢出，特别是在高精度乘以低精度运算时。
数据输入
通常使用字符串读取数据，然后将其存储到vector中。 需要注意的是，通常采用逆序存储，因为我们的运算从最低位开始。
非压位实现
void load_number(string &num_str, vector<int> &num_vec)
{
for (int i = num_str.size() - 1; i >= 0; i -- )
num_vec.push_back(num_str[i] - '0');
}
压位实现
通过代码注释可以理解压位实现的原理。
关键点在于digit_count == 9处，压位的位数需要根据实际情况调整。
void load_number(string &num_str, vector<int> &num_vec)
{
for (int i = num_str.size() - 1, current_value = 0, multiplier = 1, digit_count = 0; i >= 0; i -- )
{
current_value += (num_str[i] - '0') * multiplier;
digit_count ++ , multiplier *= 10;
if (digit_count == 9 || i == 0)
{
num_vec.push_back(current_value);
current_value = digit_count = 0;
multiplier = 1;
}
}
}
数据输出
由于输入是逆序的，输出也需要相应地逆序进行。
非压位实现
for (int i = result_vec.size() - 1; i >= 0; i -- )
cout << result_vec[i];
压位实现
压位实现中，由于最高位数字的长度不确定，需要先单独输出。 后续数字可能因取模运算而小于压位长度，因此使用printf固定输出格式，不足部分补零。
cout << result_vec.back();
for (int i = result_vec.size() - 2; i >= 0; i -- )
printf("%09d", result_vec[i]);
高精度加法
高精度加法主要分为高精度加高精度和高精度加低精度两种情况。后者使用较少，因此这里只介绍高精度加高精度的实现。
注意：算法不支持负数，正负号的处理会增加复杂度。
非压位和压位实现几乎没有本质区别，可以视为同一算法的不同参数设置，其中压1位就相当于不压位。
非压位实现
vector<int> add_big_numbers(vector<int> num1, vector<int> num2)
{
if (num1.size() < num2.size()) return add_big_numbers(num2, num1);
vector<int> result;
int carry = 0, length = num1.size();
for (int i = 0; i < length; i ++ )
{
carry += num1[i];
if (i < num2.size()) carry += num2[i];
result.push_back(carry % 10);
carry /= 10;
}
if (carry) result.push_back(carry);
return result;
}
压位实现
int base_value = 1000000000; // 压位基数
vector<int> add_big_numbers(vector<int> num1, vector<int> num2)
{
if (num1.size() < num2.size()) return add_big_numbers(num2, num1);
vector<int> result;
int carry = 0, length = num1.size();
for (int i = 0; i < length; i ++ )
{
carry += num1[i];
if (i < num2.size()) carry += num2[i];
result.push_back(carry % base_value);
carry /= base_value;
}
if (carry) result.push_back(carry);
return result;
}
高精度减法
高精度减法与加法有所不同，需要注意借位处理。最多可以借base_value位。
bool compare_numbers(vector<int> num1, vector<int> num2) // 比较两个数的大小
{
if (num1.size() != num2.size()) return num1.size() > num2.size();
for (int i = num1.size() - 1; i >= 0; i -- )
if (num1[i] != num2[i]) return num1[i] > num2[i];
return true;
}
vector<int> subtract_big_numbers(vector<int> num1, vector<int> num2) // 高精度减法
{
vector<int> result;
int borrow = 0, length = num1.size();
for (int i = 0; i < length; i ++ )
{
borrow = num1[i] - borrow;
if (i < num2.size()) borrow -= num2[i];
result.push_back((borrow + 10) % 10);
if (borrow < 0) borrow = 1; // 需要从高位借位
else borrow = 0;
}
while (result.back() == 0 && result.size() > 1) result.pop_back();
return result;
}
int main()
{
string str1, str2;
cin >> str1 >> str2;
vector<int> num1, num2, result;
for (int i = str1.size() - 1; i >= 0; i -- )
num1.push_back(str1[i] - '0');
for (int i = str2.size() - 1; i >= 0; i -- )
num2.push_back(str2[i] - '0');
if (compare_numbers(num1, num2))
result = subtract_big_numbers(num1, num2);
else
{
result = subtract_big_numbers(num2, num1);
cout << '-';
}
for (int i = result.size() - 1; i >= 0; i -- )
cout << result[i];
return 0;
}
高精度乘法
高精度乘以高精度的实现不常用，逻辑上可以推导但效率较低且调试困难。 高精度乘以低精度的实现更为实用。
高精度乘以低精度
vector<int> multiply_big_number(vector<int> num, int small_num)
{
vector<int> result;
int carry = 0, length = num.size();
for (int i = 0; i < length || carry; i ++ ) // 确保处理完所有进位
{
if (i < length) carry += num[i] * small_num;
result.push_back(carry % 10);
carry /= 10;
}
while (result.back() == 0 && result.size() > 1) result.pop_back();
return result;
}
高精度除法
高精度除以低精度的实现相对简单，而高精度除以高精度的实现较为复杂。这里提供一个思路：将除法转化为减法。
高精度除以低精度
vector<int> divide_big_number(vector<int> &num, int divisor, int &remainder)
{
vector<int> result;
remainder = 0;
for (int i = num.size() - 1; i >= 0; i -- ) // 注意从高位到低位顺序枚举
{
remainder = remainder * 10 + num[i];
result.push_back(remainder / divisor);
remainder %= divisor;
}
reverse(result.begin(), result.end()); // 结果存储顺序与实际相反，需要反转
while (result.size() > 1 && result.back() == 0) result.pop_back();
return result;
}
高精度除以高精度（早期实现）
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_SIZE = 200010;
int dividend[MAX_SIZE], divisor[MAX_SIZE], dividend_len, divisor_len;
long long quotient_count;
char dividend_str[MAX_SIZE], divisor_str[MAX_SIZE];
bool is_dividend_larger()
{
if (dividend_len != divisor_len) return dividend_len > divisor_len;
for (int i = 1; i <= dividend_len; i++)
if(dividend[i] != divisor[i]) return dividend[i] > divisor[i];
return true;
}
void subtract_divisor()
{
for (int i = 1; i <= dividend_len || i <= divisor_len; i++)
{
dividend[i] -= divisor[i];
if (dividend[i] < 0)
{
dividend[i+1]--;
dividend[i] += 10;
}
}
while(!dividend[dividend_len] && dividend_len > 1) dividend_len--;
quotient_count++;
}
int main()
{
cin >> dividend_str >> divisor_str;
dividend_len = strlen(dividend_str);
divisor_len = strlen(divisor_str);
for (int i = 1; i <= dividend_len; i++)
dividend[i] = dividend_str[dividend_len-i] - '0';
for (int i = 1; i <= divisor_len; i++)
divisor[i] = divisor_str[divisor_len-i] - '0';
while (is_dividend_larger())
{
subtract_divisor();
}
cout << quotient_count << endl;
while (dividend_len)
cout << dividend[dividend_len--];
return 0;
}
