当前位置：文江博客话题详情

如何在C++中得到大数的n次方根？

发布于 2024-08-27 22:14:07 字数 74 浏览 7 评论 0原文

是否有一个 C++ 库可以计算大数的 n 次方根（无法放入 unsigned long long 的数字）？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

娇纵 2024-09-03 22:14:07

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

回复收藏 0 原文

逐鹿 2024-09-03 22:14:07

如果您想自己编写代码，请查看有关 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

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

If you want to code this yourself, check out the Wikipedia page on nth roots:

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

The iterative algorithm is quite simple:

The nth root of a number A can be computed by the nth root algorithm, a special case of Newton's method. Start with an initial guess x(0) and then iterate using the recurrence relation

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

Stop once you've converged to the desired accuracy.

回复收藏 0 原文

心病无药医 2024-09-03 22:14:07

我猜这取决于你想要比 2^64 大多少。仅使用双精度数就可以达到 10^9 的十分之一。我用 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 进行比较得到我上面引用的错误。

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

It depends how much bigger than 2^64 you want to go, I guess. Just using doubles is good to about 1 part in 10^9. I wrote a test program in 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;
}

which produced the following output:

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

Then I compared with Wolfram Alpha for each root to get the error I quoted above.

Depending on your application, perhaps this will be good enough.

回复收藏 0 原文

木槿暧夏七纪年 2024-09-03 22:14:07

还可以尝试 MAPM 和 qd。

MAPM 用 C 编写，但也有 C++ API。 qd 用 C++ 编写，但也有 C API。

回复收藏 0 原文

慵挽 2024-09-03 22:14:07

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

    // 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);
    }

我发现这快了几分钟

Heres a perfect loop for it. I get the exact answer everytime.

    // 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);
    }

I found this to minutes faster

回复收藏 0 原文