Package de.tilman_neumann.jml.powers

Class PurePowerTest

  • public class PurePowerTest
extends 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)
    Author:
    Tilman Neumann

    • Constructor Detail

      • PurePowerTest

        public PurePowerTest()

    • Method Detail

      • test_v01

        public PurePowerTest.Result test_v01​(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. 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

        public PurePowerTest.Result test​(BigInteger N)
        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​(String[] args)
        Test.
        Parameters:
        args - ignored