c++高精度

一、高精度的定义

高精度指的是对于一些需要很高的精度的数值计算，在普通的double或float类型无法满足精度的情况下，需要使用高精度计算。

在实际应用中，例如财务计算、密码学、多项式求值等领域，高精度计算都是必不可少的。

在c++中，一般使用字符串存储高精度数，每一位都独立存储，使得精度可以任意扩展，但计算效率相对低下。

二、高精度的实现方式

1、字符串存储方式：

const int MAXN = 1e4 + 10;
const int MAXM = 1e5 + 10;

struct HignPrecision {
    int a[MAXN];
    int len;
    HignPrecision() {
        memset(a, 0, sizeof(a));
        len = 0;
    }
};

//高精度加法
HignPrecision operator + (const HignPrecision &A, const HignPrecision &B) {
    HignPrecision ret;
    int len = max(A.len, B.len);
    for (int i = 0; i  0) ret.len = len + 1;
    else ret.len = len;
    while (ret.len > 1 && ret.a[ret.len - 1] == 0) ret.len--;
    return ret;
}

2、vector存储方式：

typedef vector HignPrecision;

//高精度乘法
HignPrecision operator * (const HignPrecision &A, const HignPrecision &B) {
    HignPrecision ret;
    int len1 = A.size(), len2 = B.size();
    ret.resize(len1 + len2);
    for (int i = 0; i < len1; i++) {
        int carry = 0;
        for (int j = 0; j  1 && ret.back() == 0) ret.pop_back();
    return ret;
}

三、高精度实现的常见问题

1、进位问题：

在高精度计算的过程中，需要记得处理进位问题，例如加法中需要判断a[i] + b[i] + carry是否大于等于10。

2、借位问题：

在高精度计算的过程中，也会遇到需要处理借位问题，例如减法中需要判断a[i] – b[i] – borrow是否小于0。

3、高精度与整数间的转换问题：

在实际计算中，需要将高精度数转换为整数以便进行判断或输出，也需要将整数转换为高精度数以便进行计算。

//转化为整数
int HignPresionToInt(HignPrecision &num) {
    int res = 0, base = 1;
    for (int i = 0; i < num.len; i++) {
        res += num.a[i] * base;
        base *= 10;
    }
    return res;
}

//转化为高精度
HignPrecision IntToHignPresion(int num) {
    HignPrecision res;
    while (num) {
        res.a[res.len++] = num % 10;
        num /= 10;
    }
    return res;
}

四、高精度应用案例

1、阶乘计算：

HignPrecision factorial(int n) {
    HignPrecision res;
    res.len = 1;
    res.a[0] = 1;
    for (int i = 1; i <= n; i++) {
        HignPrecision tmp = IntToHignPresion(i);
        res = res * tmp;
    }
    return res;
}

2、多项式求值：

HignPrecision eval(HignPrecision A, HignPrecision x) {
    HignPrecision ret = IntToHignPresion(0);
    int n = A.len - 1;
    for (int i = n; i >= 0; i--) {
        HignPrecision k = ret * x;
        ret = k + IntToHignPresion(A.a[i]);
    }
    return ret;
}

3、质数判断：

HignPrecision sqrt(HignPrecision x) {
    HignPrecision l = IntToHignPresion(0), r = x, ans;
    while (l <= r) {
        HignPrecision mid = (l + r) / 2;
        if (mid * mid <= x) {
            ans = mid;
            l = mid + IntToHignPresion(1);
        } else {
            r = mid - IntToHignPresion(1);
        }
    }
    return ans;
}

bool isPrime(HignPrecision x) {
    if (x.a[0] == 0 || x == IntToHignPresion(1)) return false;
    if (x == IntToHignPresion(2) || x == IntToHignPresion(3)) return true;
    HignPrecision sqr = sqrt(x);
    for (HignPrecision i = IntToHignPresion(2); i <= sqr; i = i + IntToHignPresion(1)) {
        if (x % i == IntToHignPresion(0)) return false;
    }
    return true;
}

五、总结

高精度计算是一种必不可少的数值计算方法，在实际应用中，可以使用字符串存储或vector存储等方式进行实现。在实现的过程中，需要注意进位、借位等问题，并进行高精度与整数间的转换。高精度计算也有广泛的应用，例如阶乘计算、多项式求值、质数判断等。