nth root

[Tim Roberts]

Paul,
 
Yes, very good, on all counts.  Many thanks.
 
Tim
 

________________________________

From: Paul Rubin [mailto:"http://phr.cx"@NOSPAM.invalid]
Sent: Sun 01-Feb-09 3:53 PM
To: python-list at python.org
Subject: Re: nth root



"Tim Roberts" <t.roberts at cqu.edu.au> writes:
> Actually, all I'm interested in is whether the 100 digit numbers
> have an exact integral root, or not.  At the moment, because of
> accuracy concerns, I'm doing something like
> 
>                     for root in powersp:
>                             nroot = round(bignum**(1.0/root))
>                             if bignum==long(nroot)**root:
>                                                              .........
> which is probably very inefficient, but I can't see anything better.....

First of all, convert the bignum to a float outside of the loop.  Second, precompute
the inverses 1.0/2.0, 1.0/3.0, ....  Third, do the exponentiation and comparison only
if the float equivalent is very close.  I bet almost all the time you're spending is
in bignum to float conversion.

The article

     Daniel J. Bernstein (1998). "Detecting perfect powers in essentially
     linear time". Mathematics of Computation 67 (223): 1253-1283
     (http://cr.yp.to/papers/powers-ams.pdf)

may be of interest.
--
http://mail.python.org/mailman/listinfo/python-list