Package de.tilman_neumann.jml.powers
Class PurePowerTest
java.lang.Object
de.tilman_neumann.jml.powers.PurePowerTest
public class PurePowerTest
extends java.lang.Object
Test for pure powers (with exponent >= 2).
Thanks to Graeme Willoughby for countless suggestions, which dramatically improved performance (something like factor 200 compared to PSIQS 01)
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
PurePowerTest.Result
-
Constructor Summary
Constructors Constructor Description PurePowerTest()
-
Method Summary
Modifier and Type Method Description static void
main(java.lang.String[] args)
Test.PurePowerTest.Result
test(java.math.BigInteger N)
Much faster power test, elaborated together with Graeme Willoughby.PurePowerTest.Result
test_v01(java.math.BigInteger N)
Test if N is a pure power. The algorithm is based on {@link "https://en.wikipedia.org/wiki/Rational_sieve#Limitations_of_the_algorithm"}, with several improvements pointed out by to Graeme Willoughby: 1.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
PurePowerTest
public PurePowerTest()
-
-
Method Details
-
test_v01
Test if N is a pure power. The algorithm is based on {@link "https://en.wikipedia.org/wiki/Rational_sieve#Limitations_of_the_algorithm"}, with several improvements pointed out by to Graeme Willoughby: 1. Write an even number as N=(2^m)k (k odd). Then its p.th power (2^m)k)^p = (2^mp)k^p has the binary representation. So there is a fast bit pattern test for even N: If the number of trailing zeros in N is not equal to zero (mod p), then N is not a p.th power 2. All even powers will have been detected as squares, all powers that are multiples of three will have been detected as cubes and so on. In short, we only need to test prime exponents up to log3 N, not all exponents. 3. A square test is of course faster than an i.th power test with argument 2. - Parameters:
N
-- Returns:
- prime power representing N, or null if N is no pure power.
-
test
Much faster power test, elaborated together with Graeme Willoughby.- Parameters:
N
-- Returns:
- base and exponent, or null if N is no pure power
-
main
public static void main(java.lang.String[] args)Test.- Parameters:
args
- ignored
-