Thread: gcwsieve
View Single Post
Old 2007-04-19, 05:32   #11
geoff's Avatar
Mar 2003
New Zealand

13·89 Posts

Originally Posted by Citrix View Post
I think this will be useful, I can give it a try. Do you have any fast assembly routines for modular 64 bit addition too? (There are none built into multisieve.) I am working on a new algorithm for this project, where I can replace the multiplications with additions.
I don't know if there is anything fundamentally faster than this. Assuming 0 <= a,b < p < 2^63:

x = a+b;
if (x >= p) x -= p;

Two can be done in parallel with SSE2 and the `if' can use a conditional move instead of a branch. I think you will need to be adding two large arrays together, or adding a constant to each element of a large array before hand assembler will be much faster than what the C compiler will generate.

Btw, for the 3^16 search, your program says it can calculate 6 million primes/sec. But it takes about 100 sec to do 1 billion. So it is looking at approx 600 million primes per billion. But there are not 600 million primes in a billion, as 1/2 the numbers are even. So where the error in the calculations?
The p/sec figure is just the increase in p per second, not the number of primes calculated. I know it is not good notation :-(

The reason testing 3^16*2^(16*n)+1 is so fast is that most of the primes don't even have to be generated, the Sieve of Eratosthenes sieves numbers of the form 32*x+1, it doesn't even look at the others.
geoff is offline