Package de.tilman_neumann.jml.factor.siqs.sieve

Class Sieve03g

  • All Implemented Interfaces:
    Sieve
    public class Sieve03g
extends 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
    Author:
    Tilman Neumann

    • Constructor Detail

      • Sieve03g

        public Sieve03g()

    • Method Detail

      • getName

        public String getName()
        Specified by:
        getName in interface Sieve
        Returns:
        the name of this sieve algorithm

      • initializeForN

        public void initializeForN​(SieveParams sieveParams,
                           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
        mergedBaseSize - size of prime/power base after merging, before filtering

      • initializeForAParameter

        public void initializeForAParameter​(SolutionArrays solutionArrays,
                                    int filteredBaseSize)
        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
        filteredBaseSize - number of primes and powers use for sieving

      • sieve

        public List<Integer> sieve()
        Description copied from interface: Sieve
        Sieve for a new set of x1, x2 solutions.
        Specified by:
        sieve in interface Sieve
        Returns:
        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