This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients mark.dickinson, martin.panter, ned.deily, rhettinger, steven.daprano, tim.peters
Date 2016-08-16.18:00:04
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
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:04tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, ned.deily, steven.daprano, martin.panter
2016-08-16 18:00:04tim.peterssetmessageid: <>
2016-08-16 18:00:04tim.peterslinkissue27761 messages
2016-08-16 18:00:04tim.peterscreate