logo标签列表

如何在C++中获取大数的第n个根？

c++mathbiginteger
12

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

6个回答
10
1
没错，特别是函数 mpz_root。 - President James K. Polk
3
如果您想自己编写代码，请查看维基百科关于N次根的页面。

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

一旦达到所需的精度，请停止。
2

我猜这取决于你想要比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进行比较，以获得我上面引用的误差。

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

请注意，设置所有位的标准方法是使用~运算符，即x = ~0ULL。 - MSalters
@MSalters - 我的脸红了。谢谢。 - mtrw
0

也可以尝试使用MAPM和qd。

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

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

我发现这个比之前快了几分钟

-1

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

虽然这可能是解决问题的有价值的提示，但一个好的答案也应该展示解决方案。请编辑以提供示例代码以说明您的意思。或者，考虑将其编写为评论。 - Toby Speight
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接