12

是否有一个 C++ 库可以取大数的第 n 个根（数字不能放入 an 中unsigned long long）？

4

6 回答 6

10

您可以使用流行的开源任意精度数学库GMP 。它有C++ 绑定。

于 2010-04-08T05:33:52.850 回答
3

如果您想自己编写代码，请查看第 n 个根的 Wikipedia 页面：

http://en.wikipedia.org/wiki/Nth_root

迭代算法非常简单：

数 A 的第 n 个根可以通过第 n 个根算法计算，这是牛顿方法的一个特例。从初始猜测 x(0) 开始，然后使用递归关系进行迭代

x(k+1) = [(n - 1) * x(k) + A / x(k)^(n - 1)] / n

一旦收敛到所需的精度就停止。

于 2010-04-08T05:50:40.610 回答
2

我猜这取决于你想去比 2^64 大多少。仅使用双打对 10 ^ 9 中的大约 1 部分有好处。我用C写了一个测试程序：

#include <stdio.h>
#include <math.h>

int main(int argc, char **argv)
{
    unsigned long long x;
    double dx;
    int i;

    //make x the max possible value
    x = ~0ULL;
    dx = (double)x;
    printf("Starting with dx = %f\n", dx);
    //print the 2th to 20th roots
    for (i = 2; i < 21; i++)
    {
        printf("%dth root %.15f\n", i, pow(dx, 1.0/i));
    }
    return 0;
}

产生以下输出：

Starting with dx = 18446744073709551616.000000
2th root 4294967296.000000000000000
3th root 2642245.949629130773246
4th root 65536.000000000000000
5th root 7131.550214521852467
6th root 1625.498677215435691
7th root 565.293831000991759
8th root 256.000000000000000
9th root 138.247646578215154
10th root 84.448506289465257
11th root 56.421840319745364
12th root 40.317473596635935
13th root 30.338480458853493
14th root 23.775908626191171
15th root 19.248400577313866
16th root 16.000000000000000
17th root 13.592188707483222
18th root 11.757875938204789
19th root 10.327513583579238
20th root 9.189586839976281

然后我与每个根的Wolfram Alpha进行比较，以获得我上面引用的错误。

根据您的应用程序，也许这已经足够了。

于 2010-04-08T07:29:50.217 回答
0

也尝试MAPM和qd。

MAPM 是用 C 编写的，但也有一个 C++ API。qd 是用 C++ 编写的，但也有一个 C API。

于 2010-04-08T10:38:09.390 回答
0

这是一个完美的循环。我每次都能得到准确的答案。

    // n1 = <input>, n2 = <base limit>, nmrk = <number of cycles>
    long double n3 = 0, n2 = 0, n1 = input_number, n4 = 0;
    long double mk = 0, tptm = 0, mnk = 0, dad = 0;
    for (n3 = 0; tptm != n1 || mnk > 65535 ; nmrk++) {
        n4 += 0.19625;
        n2 += 0.15625;
        n3 += 0.015625;
        mk += 0.0073125;
        dad += 0.00390625;
        mnk = pow(n1, 1.0/(n4+n2+mk+n3+dad));
        tptm = pow((mnk), (n4+n2+mk+n3+dad));
    }
    if (tptm - n1 < 1)
    {
        uint64_t y = (tptm);
        return make_tuple(nmrk, (n1 - y), mnk);
    }

我发现这要快几分钟

于 2019-09-18T02:54:01.843 回答
-1

长除法是计算任何正实数的第 n 次根的最佳方法。它给出了计算的每个数字的最佳精度。不需要初始猜测，也不需要迭代逼近。

于 2016-02-17T11:08:01.143 回答