一、高精度的定义
高精度指的是对于一些需要很高的精度的数值计算,在普通的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 < len; i++) { ret.a[i] += A.a[i] + B.a[i]; ret.a[i + 1] = ret.a[i] / 10; ret.a[i] %= 10; } if (ret.a[len] > 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 vectorHignPrecision; //高精度乘法 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 < len2; j++) { int tmp = ret[i + j] + A[i] * B[j] + carry; ret[i + j] = tmp % 10; carry = tmp / 10; } ret[i + len2] = carry; } while (ret.size() > 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存储等方式进行实现。在实现的过程中,需要注意进位、借位等问题,并进行高精度与整数间的转换。高精度计算也有广泛的应用,例如阶乘计算、多项式求值、质数判断等。