Torbjorn Granlund <t...@gmplib.org> writes: > I just got a crazy idea. Compute the logarithm of the number (to a few > bits of precision, perhaps using table lookup). Multiply this logarithm > by k. Exponentiate using the logbase (again using a small table). > Conservatively compare to number being investigated.
And if desired, one could of course also do that the opposite way: Take the logarithm of the input number, divide by k, exponentiate, to get a small range for the highest bits of the kth root. Not sure which variant would give the best precision (i.e., lowest probability for false positives). Ah, and if we're brain storming, yet another variant would be to compute an extra limb (or maybe only half a limb) of precision when we compute the 2-adic k'th root. If the extra limb is non-zero, then the input can't be a k'th power. That's going to asymptotically a bit slower than the O(1) logarithm trick, but it can have a much smaller false positive rate. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel