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;
}