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存儲等方式進行實現。在實現的過程中，需要注意進位、借位等問題，並進行高精度與整數間的轉換。高精度計算也有廣泛的應用，例如階乘計算、多項式求值、質數判斷等。