Class Sieve03h
java.lang.Object
de.tilman_neumann.jml.factor.siqs.sieve.Sieve03h
- All Implemented Interfaces:
Sieve
public class Sieve03h 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
Version 03h:
-> unroll largest primes with the same logP value
-
Constructor Summary
Constructors Constructor Description Sieve03h()
-
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
-
Sieve03h
public Sieve03h()
-
-
Method Details
-
getName
public java.lang.String getName() -
initializeForN
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 interfaceSieve
- Parameters:
sieveParams
- basic sieve parameters for a new NbaseArrays
- the prime base, modular sqrt's, logP-values etc. before filtering out the q-parametersmergedBaseSize
- 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 interfaceSieve
- Parameters:
d
- 2 if (kN == 1) (mod 8), 1 otherwisedaParam
- d*a, where 'a' is the a-parameter and d=2 if kN==1 (mod 8), d=1 elsefilteredBaseSize
- number of primes and powers use for sievingqArray
- 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 interfaceSieve
-
sieve
Description copied from interface:Sieve
Sieve for a new set of x1, x2 solutions. -
getReport
-
cleanUp
public void cleanUp()Description copied from interface:Sieve
Release memory after a factorization.
-