20090406, 16:08  #1 
Jul 2006
Calgary
1A9_{16} Posts 
Trial Factoring Sieve?
Can someone elaborate somewhat on the trial factoring sieve used to check possible factors for primeness? It is mentioned in the GIMPS "The Math" page but not with enough details for me to implement it for myself.
I understand a regular prime sieve but I can't figure out how to apply the idea to this problem. Can you give a specific example of a particular size sieve and exactly what range of primes can be tested for and how? 
20090406, 16:15  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}·5·7 Posts 
GIMPS does not actually use a sieve to check for possible factors of Mersenne numbers, for the simple reason that any prime number can divide at most one Mersenne number with a prime exponent. Instead, GIMPS does trial factoring of 2^p  1 by all possible prime factors of the form 2kp+1, where the factors are further restricted to numbers which give a remainder of 1 or 7 when divided by 8. Restricting to just the prime possible factors is done by sieving, however, with the understanding that testing an occasional composite may be cheaper than sieving all the way until only primes remain.

20090406, 16:36  #3 
Jul 2006
Calgary
5^{2}·17 Posts 
Yes, this is what I am asking, how is this done? It eliminates many possible factors before the power/modulus test needs to be done. I am just missing some detail for how this test is implemented, so I can implement it myself.

20090406, 20:07  #4 
"William"
May 2003
Near Grandkid
2374_{10} Posts 
I don't know the actual implementation, but the straight forward obvious implementation would be two stages of sieving.
The first stage would be a Sieve of Eratosthenes to get small primes. The second stage would apply these small primes to an array where the k'th bit represents "2kp+1". One of the first 3 values of "2kp+1" is divisible by 3. Mark that and every 3rd one after it as composite. Likewise for 5, 7, etc. At the end of the second stage, the remaining "k's" represent values of 2kp+1 that might be prime (they might also be composite with smallest divisor bigger than you tested). Trial divide with these by calculating 2^n mod 2kp+1. 
20090406, 20:54  #5  
∂^{2}ω=0
Sep 2002
Repรบblica de California
11755_{10} Posts 
Quote:
And of course priorities change, depending on where the code spends most of its time ... this past weekend I finished the first working version an SSE2based TF modular powering routine for candidate factors up to 78 bits  that runs 23x faster on 32bit x86 than the pureinteger analog does, so now the sieving work (which was between 2050% of the total runtime) has suddenly become an important furtheroptimization candidate again. Thoughts on further speeding the sieve: The main problem with the sieve bitclearing code at present is that I process one small prime at a time, clear all the bits corresponding to q`s divisible by that prime, then proceed to the next small prime. For a sieve consisting of all primes less than (say) 1 million that means around 70000 sweeps through the sieve bitarray. Even if that is designed to fit in L1 cache (it is) that's a lot of memory traffic, and there is (at present) no a priori way to prevent a bit from getting "cleared" multiple times. I've been contemplating how to address these issues, and am thinking that perhaps some kind of heapbased approach might work: As one computes the bits hit by each multiple of the current sieving prime, push an integer corresponding to the bit location into a heap, which is designed to only accept "new" values, i.e. to ignore values already in the heap. At the end of smallprimes processing, just pop one value at a time off the heap, and clear (just once now) the corresponding bit of the sieve. But it seems that is just robbing Peter to pay Paul, as one has simply exchanged redundant bitclears with redundantheapelementpushignores. Last fiddled with by ewmayer on 20090406 at 20:55 

20090406, 22:13  #6 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
IIRC, the current GIMPS software's TF potentialfactor sieving consists of testing only the nonguaranteedcomposite residue classes mod 210 (in addition to the modulo 8 requirements). I.e., 1 mod 210, 11 mod 210, 13 mod 210, ..., 199 mod 210, 209 mod 210.
Last fiddled with by cheesehead on 20090406 at 22:18 
20090406, 22:19  #7  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2×7^{3}×17 Posts 
Quote:
Observe that the bit pattern for a given prime p repeats with periodicity p (obviously!) and that on a nbit machine, the word pattern repeats every p words. So, sieve p words with prime p then logicaland that word pattern into the remainder of the sieve. The idea is to replace bit addressing, which most machines are bad at, with (possibly vectorizable) word operations. Note that exactly the same approach applies when p is the product of small primes, which may be useful for the smallest primes, which are the ones that take most of the time anyway. As long as p is within a reasonable range, p words is relatively small amount of storage. Who is this Peter guy anyway? Paul 

20090406, 22:47  #8  
∂^{2}ω=0
Sep 2002
Repรบblica de California
5×2,351 Posts 
Quote:
I think it really boils down to making the rote bitclearing as cycleefficient as absolutely possible ... this coming weekend I will look at using SSE2 not just (in the floatingpoint sense) for the modular powering but (in 128bit integer ALU mode) for the bitclearing. Quote:
Last fiddled with by ewmayer on 20090406 at 22:48 

20090406, 23:17  #9 
P90 years forever!
Aug 2002
Yeehaw, FL
1FE5_{16} Posts 

20090406, 23:24  #10 
"William"
May 2003
Near Grandkid
946_{16} Posts 
Most of the "double markings" are going to be numbers that were previously marked with tiny primes. I was going to suggest a 3 spoke wheelperprime so that when marking multiples of q you could avoid marking multiples of 3q, 5q, and 7q. But the handful of hits suggests that at most a 1 or 2 spoke wheel is useful. Note that "residues mod 210" is an alternative implementation of the same idea  avoiding duplicate marking for multiples of 3, 5, and 7.
Last fiddled with by wblipp on 20090406 at 23:24 
20090406, 23:57  #11  
∂^{2}ω=0
Sep 2002
Repรบblica de California
5×2,351 Posts 
Quote:
George, what is a typical smallprime limit used by your code, and roughly what fraction of the TF time does it spend in sieverelated operations? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Constructing a sieve for trial factors  davieddy  Math  48  20090707 19:42 
How far to do trial factoring  S485122  PrimeNet  1  20070906 00:52 
trial factoring and P1  jocelynl  Math  8  20060201 14:12 
How to only do Trial Factoring?  michael  Software  23  20040106 08:54 
About trial factoring  gbvalor  Math  4  20030522 02:04 