nth root

[Peter Pearson]

On Sun, 1 Feb 2009 15:36:43 +1000, Tim Roberts <t.roberts at cqu.edu.au> wrote:
>
> 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.....

You've gotten several promising leads on this thread, but
here's one more thing that might help.  Note that if 
c == b**13, then c%p == pow( b%p, 13, p ) for any prime p.
So if you have a 100-digit c and a "candidate" 13-th root b,
and you choose p = 101 (for example), a false b has only a 1%
chance of passing the c%p == pow( b%p, 13, p ) test, which
might save some fraction of the cost of whatever more
rigorous test you subsequently apply.

-- 
To email me, substitute nowhere->spamcop, invalid->net.