On Sun, 1 Feb 2009 15:36:43 +1000, Tim Roberts <t.robe...@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. -- http://mail.python.org/mailman/listinfo/python-list
