写在前面
前几天给出了长除法的Python实现, 但是C++毕竟还是要更快的, 只是没有精度支持而已, 后来发现一个叫GMP的库可以实现, 下面来看下具体操作.
安装与构建
如果安装过llvm或者gcc, GMP其实是会附带安装的, 因为这些C编译器都需要GMP作为依赖.
这里我发现一个很奇怪的现象, 由于我电脑中有三种C++编译器, 分别是
xcode自带的clang(被alias为gcc, 14.0.0)
通过brew安装的clang(llvm, 15.0.6)
通过brew安装的gcc(12.2.0)
通过ChatGPT给出的GMP实例:(这个比较复杂, 后面直接用c++的mpz_class替代了)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include "gmp.h"
int main(int argc, char const *argv[]) {
// Declare two arbitrary-precision integers
mpz_t x, y;
// Initialize the integers
mpz_init(x);
mpz_init(y);
// Set the value of x to 1234567890
mpz_set_str(x, "1234567890", 10);
// Set the value of y to 9876543210
mpz_set_str(y, "9876543210", 10);
// Declare a third arbitrary-precision integer to store the result
mpz_t result;
mpz_init(result);
// Perform the multiplication
mpz_mul(result, x, y);
// Print the result
std::cout << "Result: " << result << std::endl;
// Clear the variables to free memory
mpz_clear(x);
mpz_clear(y);
mpz_clear(result);
return 0;
}
编译方式采用:
clang++ test.cpp -lgmp -lgmpxx -o main
可以得到:
Result: 12193263111263526900
但是, 采用g++总是会报错:
Undefined symbols for architecture arm64:
"__ZlsRSoPK12__mpz_struct", referenced from:
_main in ccXaHfVB.o
ld: symbol(s) not found for architecture arm64
collect2: error: ld returned 1 exit status
于是我就感觉MacOS上的gcc还是不够完善的, 这样一种常用的库竟然找不到链接库, 十分费解..
另一种猜测, clang来编译得到的Gcc, 所以gmp也是clang编译得到的, 而gcc与clang不兼容, 于是就找不到符号了.
长除法
有了上面的方法, 用C++实现任意长度的整数平方根应该是没有任何问题了. (后续可以研究一下高精度计算算法, 看起来很经典)
#include <iostream>
#include <vector>
#include <typeinfo>
#include <gmp.h>
#include <gmpxx.h>
using namespace std;
ostream& operator<<(ostream& os, const vector<mpz_class> v) {
for (auto i : v) os << i << " ";
return os << endl;
}
int find_nice(mpz_class R, mpz_class b) {
int l{}, r{9}, mid{};
while (l <= r) {
int mid = l + (r - l) / 2;
if ((20 * b + mid) * mid > R)
r = mid - 1;
else
l = mid + 1;
}
return l - 1;
}
mpz_class mySqrt(mpz_class n) {
int i{};
vector<mpz_class> a(105, 0);
// Dividing the number into segments
while (n) {
a[i++] = n % 100;
n /= 100;
}
mpz_class quotient, dividend, reminder, tmp;
for (int j = i - 1; j >= 0; --j) {
dividend = reminder * 100 + a[j]; // update dividend
int tmp = find_nice(dividend, quotient);
reminder = dividend - (20 * quotient + tmp) * tmp;
quotient = quotient * 10 + tmp;
}
return quotient;
}
void t2() {
mpz_class n;
n = "500000000000000";
cout << mySqrt(n) << endl;//22360679
}
int main(int argc, char const* argv[]) {
t2();
return 0;
}
编译选项:
clang++ long_division_with_gmp.cpp -lgmpxx -lgmp -std=c++14 && ./a.out
输出:
22360679
如果要实现小数点后任意位数, 这里以$\sqrt5$为例, 直接注释掉29~32行, 然后对数组赋值即可:
i = 101;
a[i - 1] = 5;
编译得到:
22360679774997896964091736687312762354406183596115257242708972454105209256378048994144144083787822749
对照一下之前用Python得到的结果发现, 完全一样!