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

      public 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. 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​(java.math.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​(java.lang.String[] args)
      Test.
      Parameters:
      args - ignored