Как получить n-й корень больших чисел в С++?

Ответ 1

Вы можете использовать GMP, популярную математическую библиотеку произвольной точности с открытым исходным кодом. Он имеет привязки С++.

Ответ 2

Если вы хотите самим закодировать это, просмотрите страницу Википедии на n-ом корне:

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

Итеративный алгоритм довольно прост:

n-й корень из числа A может быть вычислен с помощью n-го алгоритма корня, частного случая метода Ньютона. Начните с начальной догадки x (0), а затем итерации, используя рекуррентное отношение

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

Остановитесь, как только вы достигнете желаемой точности.

Ответ 3

Это зависит от того, насколько больше, чем 2 ^ 64 вы хотите пойти, я думаю. Просто использование удваивается до 1 части в 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 для каждого корня, чтобы получить приведенную выше ошибку.

В зависимости от вашего приложения, возможно, это будет достаточно хорошо.

Ответ 4

Попробуйте также MAPM и qd.

MAPM написан на C, но также имеет С++ API. qd записывается в С++, но также имеет C API.

Ответ 5

Вот идеальная петля для этого. Я получаю точный ответ каждый раз.

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

Я нашел это на несколько минут быстрее

Ответ 6

Метод с длинным делением - лучший метод вычисления n-го корня из любого положительного действительного числа. Это дает максимальную точность вычисляемой цифры. Нет первоначального предположения и не требуется итеративного приближения.