N-й корень BigInteger

Question

Я использую объект BigInteger. При нормальных ints или longs я могу использовать Math.pow (число, 1/n-й корень), чтобы получить n-й корень. Однако это не будет работать с BigInteger. Есть ли способ, которым я могу это сделать?

На самом деле, мне не нужен корень, чтобы знать, является ли это идеальной силой. Я использую это, чтобы выяснить, является ли данный BigInteger идеальным квадратом/кубом/и т. Д.

Answer 1

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

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.

Answer 2

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

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

Answer 3

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

Answer 4

вы можете использовать бинарный поиск

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

Algo:

1. Сначала вычислим предел yymax

• Я хотел бы использовать 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) может быть сделано bina гу питание
• или с одного циклом для малого n

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

• если (x<0) то n должно быть нечетным, очевидно, и y<0
• так, если не возвращать ложные
• еще отрицают 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 тип данных
• , как вы можете видеть, что вам нужно только основные aithmetic и битовые операции, как +,<,==,<<,>>,|,^ (последнее XOR не власть)