N-й корень от BigInteger

Метод Ньютона отлично работает с целыми числами; здесь мы вычисляем наибольшее число s, для которого s ^k не превышает n, предполагая, что оба k и n положительны:

function iroot(k, n)
    k1 := k - 1
    s := n + 1
    u := n
    while u < s
        s := u
        u := ((u * k1) + n // (u ** k1)) // k
    return s

Например, iroot(4, 624) возвращает 4, а iroot(4, 625) возвращает 5. Затем вы можете выполнить возведение в степень и проверить результат:

function perfectPower(k, n)
    return (k ** iroot(k, n)) == n

Например, perfectPower(2, 625) и perfectPower(4, 625) оба истинны, а perfectPower(3, 625) - ложно.

Я оставлю вам перевод на Java BigInteger.

Для начала вы можете использовать бинарный поиск, легко реализовать let:

• x будь твоим старшим
• n n-я степень, которую вы хотите проверить

поэтому вы хотите проверить, есть ли y такое, что y^n=x и для начала предполагают x>=0 Алгоритм выглядит следующим образом:

1. первое вычисление y предела ymax

   Я бы использовал 2^(log2(x)/n), это число с (bits used for x)/n, поэтому ymax^n имеет такое же количество битов, как x. Итак, сначала посчитайте биты x, а затем разделите их на n.

   for (ymax=1,i=1;i<=x;i<<=1) ymax++; ymax=(ymax/n);
   

   теперь ymax - это количество бит, y необходимо проверить до

2. поиск по корзине

    for(m=1<<ymax,y=0;m;m>>=1)
     {
     y|=m;
     if (integer_pow(y,n)>x) y^=m;
     }
    return (integer_pow(y,n)==x);
   

   integer_pow(y,n) может выполняться с помощью двоичного питания или с помощью одиночного цикла for для малых n

3. добавить обработку знака

   если (x<0), то n, очевидно, должно быть нечетным, а y<0 поэтому, если не вернуть false, иначе отрицать x, а также окончательный y результат.

[edit1] Вот простой пример C ++:

bool is_root(DWORD &y,DWORD x,DWORD n) // y=x^(1/n) return true if perfect nth root
    {
    DWORD i,p,m; y=x;
    if (n==0) { y=0; return (x==0); }
    if (n==1) { y=x; return (x!=0); }
    for (i=1,m=1;m<x;i++,m<<=1); m=1<<(i/n); // compute the y limit
    for (y=0;m;m>>=1) // bin search through y
        {
        y|=m;
        for (p=y,i=1;i<n;i++) p*=y; // p=y^n
        if (p>x) y^=m; // this is xor not power!!!
        }
    for (p=y,i=1;i<n;i++) p*=y; // p=y^n
    return (p==x);
    }

поэтому просто преобразуйте DWORD в свой тип данных bigint, как видите, вам нужны только базовые арифметические и битовые операции, такие как +,<,==,<<,>>,|,^ (последнее - XOR, а не мощность)

Есть также другие возможности сделать это для некоторого вдохновения, проверьте это (и все там подссылки):

• Степень возведения в квадрат для отрицательных показателей степени

Так, например, вы можете даже избавиться от * операций (как я сделал в подссылке 16T sqrt, представленной в одной из подссылок (заголовок: ... только один цикл)), что является огромным ускорением для bigints.

Я решил проблему с этой функцией, которую получил из формулы Ньютона

public boolean perfectPower(BigDecimal a, double n){
    BigDecimal[] x = new BigDecimal[40];
    x[0] = BigDecimal.ONE;
    int digits = a.toString().length();
    System.out.println(digits);
    int roundTo = digits + 1;
    for(int k = 1; k < 40; k++){
        x[k] = (x[k - 1]
                .multiply(BigDecimal.valueOf((int)n - 1))
                .add(a
                        .divide(x[k - 1]
                        .pow((int)n - 1), new MathContext(roundTo, RoundingMode.HALF_EVEN))))
                .multiply(BigDecimal.valueOf(1/n));
    }
    String str = x[39].toString();
    return str.substring(str.indexOf(".") + 1, str.indexOf(".") + 6).equals("00000");
}

Разложите число на множители и посмотрите, сколько существует различных факторов. Если есть только один, это полная n-я степень, где n - кратность множителя. Могут быть более эффективные методы, но они гарантированно работают.