Class TDiv63Inverse

java.lang.Object
de.tilman_neumann.jml.factor.FactorAlgorithm
de.tilman_neumann.jml.factor.tdiv.TDiv63Inverse

public class TDiv63Inverse
extends FactorAlgorithm
Trial division factor algorithm replacing division by multiplications. Instead of dividing N by consecutive primes, we store the reciprocals of those primes, too, and multiply N by those reciprocals. Only if such a result is near to an integer we need to do a division. Assuming that we want to identify "near integers" with a precision of 2^-d. Then the approach works for primes p if bitLength(p) >= bitLength(N) - 53 + d. For some unknown reason, storing and reusing the quotient q = (long) (N*r + DISCRIMINATOR) only helps in TDiv31Inverse but not in TDiv63Inverse.
  • Field Summary

    Fields inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    NUM_PRIMES_FOR_31_BIT_TDIV, tdivLimit
  • Constructor Summary

    Constructors
    Constructor Description
    TDiv63Inverse​(int factorLimit)
    Create a trial division algorithm that is capable of finding factors up to factorLimit.
  • Method Summary

    Modifier and Type Method Description
    void factor​(java.math.BigInteger Nbig, SortedMultiset<java.math.BigInteger> primeFactors)
    Decomposes the argument N into prime factors.
    int findSingleFactor​(long N)  
    java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
    Find a single factor of the given N, which is composite and odd.
    java.lang.String getName()  
    static void main​(java.lang.String[] args)
    Test.
    TDiv63Inverse setTestLimit​(int pLimit)
    Set the upper limit of primes to be tested.

    Methods inherited from class de.tilman_neumann.jml.factor.FactorAlgorithm

    factor, getDefault, searchFactors

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • TDiv63Inverse

      public TDiv63Inverse​(int factorLimit)
      Create a trial division algorithm that is capable of finding factors up to factorLimit.
      Parameters:
      factorLimit -
  • Method Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in class FactorAlgorithm
      Returns:
      The name of the algorithm, possibly including important parameters.
    • setTestLimit

      public TDiv63Inverse setTestLimit​(int pLimit)
      Set the upper limit of primes to be tested.
      Parameters:
      pLimit - the limit; must be smaller than the factorLimit parameter passed to the constructor
      Returns:
      this
      Throws:
      java.lang.IllegalStateException - if pLimit > factorLimit
    • factor

      public void factor​(java.math.BigInteger Nbig, SortedMultiset<java.math.BigInteger> primeFactors)
      Description copied from class: FactorAlgorithm
      Decomposes the argument N into prime factors.
      Overrides:
      factor in class FactorAlgorithm
      Parameters:
      Nbig - Number to factor.
      primeFactors - a map to which found factors are added
    • findSingleFactor

      public java.math.BigInteger findSingleFactor​(java.math.BigInteger N)
      Find a single factor of the given N, which is composite and odd. This implementation will return 1 if the smallest factor of N is greater than pLimit.
      Specified by:
      findSingleFactor in class FactorAlgorithm
      Parameters:
      N - number to be factored.
      Returns:
      factor
    • findSingleFactor

      public int findSingleFactor​(long N)
    • main

      public static void main​(java.lang.String[] args)
      Test.
      Parameters:
      args - ignored