3.3 乘法
高精度乘法运用竖式计算的思想，用一个数的某一位乘以另一个数的所有位。
例如：对于1234 * 56，我们用数组a和b分别存储1234和56，用数组c存储结果。
a[3] a[2] a[1] a[0]
x b[1] b[0]
________________________________________________________
a[3]b[0] a[2]b[0] a[1]b[0] a[0]b[0]
a[3]b[1] a[2]b[1] a[1]b[1] a[0]b[1]
________________________________________________________
c[4] c[3] c[2] c[1] c[0]
通过这个我们可以找规律，假设a,b和c的下标分别为i,j和k，那么k=i+j。
综上，我们可以写出以下代码：
void multiply(string& charA, string& charB)
{
int a[256] = {0}, b[256] = {0};
init(charA, a);
init(charB, b);
int lenA = charA.length(), lenB = charB.length();
int c[256] = {0};//c是结果
int maxlen = lenA + lenB;
for (int i = 0; i < lenA; i++)// 类似竖式计算
{
for (int j = 0; j < lenB; j++)
{
c[i + j] = a[i] * b[j];
c[i + j + 1] += c[i + j] / 10;//进位
c[i + j] %= 10;//进位
}
}
//删除前导零
while (c[maxlen - 1] == 0 && maxlen > 1) maxlen--;
//输出
for (int i = maxlen - 1; i >= 0; i--)
{
cout << c[i];
}
cout << endl;
}
3.4 除法
高精度除法也利用了竖式除法的思想。核心是逐位试商法。
-
①从被除数的第一位开始，用此数除以除数，得出商和余数
-
②用得出的余数与被除数的下一位数字结合继续除以除数，以此类推
3.4.1 高精度除以低精度
//一位数一位数地与除数相除，余数乘10加入下一位上
void div1(string charA, int x)//x是除数
{
int lenA = charA.size();
int a[256] = {0};
init(charA, a);
int c[256] = {0};
int remainder = 0;//余数
for (int i = lenA - 1;i >= 0;i--)
{
remainder = remainder * 10 + a[i]; //模拟竖式除法中的落位
c[i] = remainder / x;
remainder %= x;
}
//删除前导零
while (c[lenA - 1] == 0 && lenA > 1) lenA--;
//输出结果
for (int i = lenA - 1; i >= 0; i--)
{
cout << c[i];
}
//如果余数不为0，输出余数
if(remainder)
{
cout << "\nremainder: " << remainder << endl;
}
}
3.4.2 高精度除以高精度
先定义一个函数isGreater，作用如下：
//被除数a的最低位下标为min_dg。lenB是除数b的长度，避免反复计算。
//此函数用于判断a最低位是否能再减去除数b而保持非负
inline bool isGreater(int a[], int b[], int min_dg, int lenB)
{
//若被除数剩余部分比除数长，则返回true
if (a[min_dg + lenB] != 0) return true;
//从高位到低位，逐位比较
for (int i = lenB - 1; i >= 0; i--)
{
if (a[min_dg + i] > b[i]) return true;
if (a[min_dg + i] < b[i]) return false;
}
//相等的情况也返回true
return true;
}
除法函数：
void div2(string charA, string charB)
{
//c是商，d是被除数的剩余部分，算法结束之后即为余数
int a[256] = {0}, b[256] = {0}, c[256] = {0}, d[256] = {0};
int lenA = charA.length(), lenB = charB.length();
init(charA, a);init(charB, b);
//若除数为0，直接结束。
if (lenB == 0)
{
cout << "除数不能为0！" << endl;
return;
}
//一开始，除数的剩余部分是它本身
for (int i = 0; i < lenA; i++)
{
d[i] = a[i];
}
//模拟竖式长除法的过程：从下标lenA-lenB开始，从高位到低位计算商
//如果觉得太抽象，可以手算一遍竖式除法加以理解
for (int i = lenA - lenB; i >= 0; i--)
{
//判断第i位（也即min_dg）是否为最低位
//也即是否可以再减去除数而保持非负
while(isGreater(d, b, i, lenB))
{
//高精度减法
for (int j = 0; j < lenB; j++)
{
d[i + j] -= b[j];
if (d[i + j] < 0)
{
d[i + j + 1] -= 1;
d[i + j] += 10;
}
}
c[i] += 1;
}
}
//删除前导零
while (c[lenA - 1] == 0 && lenA > 1) lenA--;
//输出结果
for (int i = lenA - 1; i >= 0; i--)
{
cout << c[i];
}
//若有余数则输出余数
if(d[0])
{
cout << "\nThe remainder is: " << d[0] << endl;
}
}