Message272871
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 ;-) |
|
Date |
User |
Action |
Args |
2016-08-16 18:00:04 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson, ned.deily, steven.daprano, martin.panter |
2016-08-16 18:00:04 | tim.peters | set | messageid: <1471370404.93.0.0558794982235.issue27761@psf.upfronthosting.co.za> |
2016-08-16 18:00:04 | tim.peters | link | issue27761 messages |
2016-08-16 18:00:04 | tim.peters | create | |
|