"Tim Roberts" <t.robe...@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
