Message 272871 - Python tracker (original) (raw)

Thanks, Mark! I had worked out the floor_nroot algorithm many years ago, but missed the connection to the AM-GM inequality. As a result, instead of being easy, proving correctness was a pain that stretched over pages. Delighted to see how obvious it can be!

Just FYI, this was my "cheap" suggestion:

from fractions import Fraction

def rootn(x, n):
    g = Fraction(x**(1.0/n))
    g = ((n-1)*g + Fraction(x)/g**(n-1)) / n
    return float(g)

For fun, I ran that and your nroot over several million random cases with x of the form

ldexp(random(), randrange(-500, 501))

and n in randrange(2, 501).

They always delivered the same result, which differed from x**(1/n) about a quarter of the time. On average nroot took about 3.7 times longer.

But reducing the n range to randrange(1, 100), over half the time the (common) result differed from x**(1/n), and nroot was significantly faster.

Moral of the story: none I can see ;-)