Tim Peters added the comment:
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 ;-)
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue27761>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
