详解C/C++高精度算法的简单实现

简介

高精度算法是指在计算机上处理大数（比int、long long等数据类型的范围还要大）时，用特殊的算法进行计算的技术，它可以大大提高程序的精度。本文将详细讲解在C/C++语言中实现高精度算法的方法。

实现思路

实现高精度算法的主要思路是将大数拆分成多个小数，每个小数用数组存储数据，然后借助数组的运算来实现对大数的计算。下面是一些常用的方法：

1. 将数字转换成数组。例如：数字1937可转换为数组{1,9,3,7}来进行计算。
2. 实现数组的加减乘除运算。算法的本质是遵循竖式运算法则，一边相加、相减、相乘、相除，一边进位、退位、进位等操作，类似于小学两位数的竖式运算。
3. 将结果数组转换成数字。例如：数组{1,9,3,7}的值为1937。

实现代码

数字转数组

void numToArr(int num, int* arr, int& len) {
    len = 0;
    while (num) {
        arr[len++] = num % 10;
        num /= 10;
    }
    reverse(arr, arr + len);  // 反转数组
}

数组转数字

int arrToNum(int* arr, int len) {
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum = sum * 10 + arr[i];
    }
    return sum;
}

高精度加法

void highAdd(int* a, int* b, int* c, int len1, int len2, int& len3) {
    len3 = max(len1, len2);
    int carry = 0;
    for (int i = 0; i < len3; i++) {
        int sum = carry;
        if (i < len1) sum += a[len1 - i - 1];
        if (i < len2) sum += b[len2 - i - 1];
        c[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry != 0) {
        c[len3] = carry;
        len3++;
    }
}

高精度减法

void highSub(int* a, int* b, int* c, int len1, int len2, int& len3) {
    len3 = max(len1, len2);
    int carry = 0;
    for (int i = 0; i < len3; i++) {
        int diff = carry;
        if (i < len1) diff += a[len1 - i - 1];
        if (i < len2) diff -= b[len2 - i - 1];
        if (diff < 0) {
            carry = -1;
            c[i] = diff + 10;
        } else {
            carry = 0;
            c[i] = diff;
        }
    }
    while (len3 > 1 && c[len3 - 1] == 0) len3--; // 去掉高位的0
}

高精度乘法

void highMul(int* a, int* b, int* c, int len1, int len2, int& len3) {
    len3 = len1 + len2;
    memset(c, 0, len3 * sizeof(int)); // 初始化为0
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    while (len3 > 1 && c[len3 - 1] == 0) len3--; // 去掉高位的0
}

高精度除法

void highDiv(int* a, int b, int* c, int len1, int& len3) {
    len3 = len1;
    long long tmp = 0; // 用long long存储计算结果，避免溢出
    for (int i = 0; i < len1; i++) {
        tmp = tmp * 10 + a[i];
        c[i] = tmp / b;
        tmp %= b;
    }
    while (len3 > 1 && c[len3 - 1] == 0) len3--; // 去掉高位的0
}

示例说明

示例1：计算阶乘

// 阶乘计算（利用高精度）
int main() {
    const int MAXN = 1000;
    int a[MAXN], b[MAXN], c[MAXN], d[MAXN], len1, len2, len3, len4;
    int n;
    scanf("%d", &n);
    numToArr(1, a, len1);
    for (int i = 1; i <= n; i++) {
        numToArr(i, b, len2);
        highMul(a, b, c, len1, len2, len3);
        memcpy(a, c, len3 * sizeof(int)); // 等价于 for (int j = 0; j < len3; j++) a[j] = c[j];
        len1 = len3;
    }
    printf("%d! = ", n);
    for (int i = len1 - 1; i >= 0; i--) {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

输入：n=5.

输出：5!=120.

示例2：计算斐波那契数列

// 斐波那契数列（利用高精度）
int main() {
    const int MAXN = 1000;
    int a[MAXN], b[MAXN], c[MAXN], len1, len2, len3;
    int n;
    scanf("%d", &n);
    numToArr(1, a, len1);
    numToArr(1, b, len2);
    for (int i = 3; i <= n; i++) {
        highAdd(a, b, c, len1, len2, len3);
        memcpy(a, b, len2 * sizeof(int));
        memcpy(b, c, len3 * sizeof(int));
        len1 = len2;
        len2 = len3;
    }
    printf("Fibonacci(%d) = ", n);
    for (int i = len3 - 1; i >= 0; i--) {
        printf("%d", c[i]);
    }
    printf("\n");
    return 0;
}

输入：n=7.

输出：Fibonacci(7)=13.