Class Sieve03g

java.lang.Object
de.tilman_neumann.jml.factor.siqs.sieve.Sieve03g
All Implemented Interfaces:
Sieve

public class Sieve03g
extends java.lang.Object
implements Sieve
Advanced non-segmented sieve implementation. Version 03: -> The smallest primes are not used for sieving. A prime p makes an overall contribution proportional to log(p)/p to the sieve array, but the runtime of sieving with a prime p is proportional to sieveArraySize/p. Thus sieving with small primes is less effective, and skipping them improves performance. -> Let counters run down -> simpler termination condition -> Faster zero-initialization of sieve array with System.arrayCopy(). Version 03b: -> Initialize sieve array such that a sieve hit is achieved if (logPSum & 0x80) != 0, and then use the or-trick in sieve:collect. -> precompute minSolutionCounts for all p -> allocate sieveArray with pMax extra entries to save size checks Version 03c: -> sieve positive x-values first, then negative x-values. Surprising improvement. Version 03d: -> Special treatment for large primes having 0-1 solutions for each of x1, x2 inside the sieve array. This is the biggest performance improvement since the 1.0.2 release! Version 03e: -> Collect smooth Q(x) for pos/neg x independently -> another small improvement Version 03f: -> Initialization is be done independently for pos/neg x, too -> now only 1 sieve array is needed! Version 03g: -> further unrolling of large primes -> sieve with all primes as if they have 2 x-solutions
  • Constructor Summary

    Constructors
    Constructor Description
    Sieve03g()  
  • Method Summary

    Modifier and Type Method Description
    void cleanUp()
    Release memory after a factorization.
    java.lang.String getName()  
    SieveReport getReport()  
    void initializeForAParameter​(int d, java.math.BigInteger daParam, SolutionArrays solutionArrays, int filteredBaseSize, int[] qArray)
    Set (filtered) prime base and smallest x1, x2 solutions for a new a-parameter.
    void initializeForN​(SieveParams sieveParams, BaseArrays baseArrays, int mergedBaseSize)
    Initialize for a new N.
    void setBParameter​(java.math.BigInteger b)
    Pass the b-parameter to the sieve.
    java.lang.Iterable<SmoothCandidate> sieve()
    Sieve for a new set of x1, x2 solutions.

    Methods inherited from class java.lang.Object

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

    • Sieve03g

      public Sieve03g()
  • Method Details

    • getName

      public java.lang.String getName()
      Specified by:
      getName in interface Sieve
      Returns:
      the name of this sieve algorithm
    • initializeForN

      public void initializeForN​(SieveParams sieveParams, BaseArrays baseArrays, int mergedBaseSize)
      Description copied from interface: Sieve
      Initialize for a new N. In PSIQS, this method is called for each thread, so things that can be computed before should be computed before.
      Specified by:
      initializeForN in interface Sieve
      Parameters:
      sieveParams - basic sieve parameters for a new N
      baseArrays - the prime base, modular sqrt's, logP-values etc. before filtering out the q-parameters
      mergedBaseSize - size of the prime base (after eventually merging primes and powers), before filtering q-parameters
    • initializeForAParameter

      public void initializeForAParameter​(int d, java.math.BigInteger daParam, SolutionArrays solutionArrays, int filteredBaseSize, int[] qArray)
      Description copied from interface: Sieve
      Set (filtered) prime base and smallest x1, x2 solutions for a new a-parameter.
      Specified by:
      initializeForAParameter in interface Sieve
      Parameters:
      d - 2 if (kN == 1) (mod 8), 1 otherwise
      daParam - d*a, where 'a' is the a-parameter and d=2 if kN==1 (mod 8), d=1 else
      filteredBaseSize - number of primes and powers use for sieving
      qArray - the q-parameters whose product is the a-parameter
    • setBParameter

      public void setBParameter​(java.math.BigInteger b)
      Description copied from interface: Sieve
      Pass the b-parameter to the sieve.
      Specified by:
      setBParameter in interface Sieve
    • sieve

      public java.lang.Iterable<SmoothCandidate> sieve()
      Description copied from interface: Sieve
      Sieve for a new set of x1, x2 solutions.
      Specified by:
      sieve in interface Sieve
      Returns:
      (something like a) list of sieve locations x where Q(x) is smooth enough to be passed to trial division
    • getReport

      public SieveReport getReport()
      Specified by:
      getReport in interface Sieve
      Returns:
      description of the durations of the individual sub-phases
    • cleanUp

      public void cleanUp()
      Description copied from interface: Sieve
      Release memory after a factorization.
      Specified by:
      cleanUp in interface Sieve