BigInteger的第N个根 [英] Nth root of BigInteger

问题描述

我正在使用BigInteger对象.在使用普通整数或long的情况下，我可以使用Math.pow(number，1/nth root)来获得第n个根.但是，这不适用于BigInteger.有办法吗?

I'm using a BigInteger object. With normal ints or longs, I can use Math.pow(number, 1/nth root) to get the nth root. However, this will not work with a BigInteger. Is there a way I can do this?

我实际上不需要根源，只是想知道它是否是完美的力量.我正在用它来确定给定的BigInteger是否是完美的正方形/立方体/等.

I do not actually need the root, just to know if it is a perfect power. I'm using this to figure out if the given BigInteger is a perfect square/cube/etc.

推荐答案

牛顿方法与整数完美兼容；在这里，我们假设 s ^k 不超过 n 的最大数量 s 和 n 是肯定的:

Newton's method works perfectly well with integers; here we compute the largest number s for which s^k does not exceed n, assuming both k and n are positive:

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.然后，您可以执行幂运算并检查结果:

For instance, iroot(4, 624) returns 4 and iroot(4, 625) returns 5. Then you can perform the exponentiation and check the result:

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

例如， perfectPower(2，625)和 perfectPower(4，625)都是正确的，但 perfectPower(3，625)是错误的.

For instance, perfectPower(2, 625) and perfectPower(4, 625) are both true, but perfectPower(3, 625) is false.

我将它留给您翻译成Java BigInteger.

I'll leave it to you to translate to Java BigInteger.

这篇关于BigInteger的第N个根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！