View Single Post
Old 2007-12-15, 01:28   #4
geoff's Avatar
Mar 2003
New Zealand

13·89 Posts

Originally Posted by monst View Post
Hello Rogue,
Also... a performance question for you and Geoff:
Several years back, you mentioned that it was more efficient to sieve GCs and GWs at the same time in MultiSieve. Is this also true for gcwsieve? ... or would it be more efficient to sieve them separately?
For gcwsieve, in theory, there is a small advantage to sieving Cullen and Woodall together: it saves the time to generate the candidate prime factors p; saves one modular inverse per p; and often reduces the size of the greatest gap between exponents (because there are more exponents over the same interval).

However in practice when there are many thousands of exponents in the sieve the difference is hardly noticeable, and on some machines the effect of the extra L2 cache space used (8 bytes for each Cullen and each Woodall in the sieve) is more important. There might be more of a difference when there is only a small number of exponents in the sieve, less than a few hundred say, but gcwsieve is not optimised for that situation anyway.

The only real answer is to test it for yourself and see which method is faster.

Originally Posted by rogue
I sent the code to Geoff a while ago, but he hasn't implemented it yet. In lieu of that you can use MultiSieve to sieve up to a point where p > max n, then switch to gcwsieve
I have the code for testing primes p < max exponent n, but there is still more that needs to be done to generate the sieve from scratch.

When I get time I plan to make it possible for gcwsieve to generate a sieve from scratch, if only because the only way to do that in Linux is to run MultiSieve in a Windows emulator, or by trial factoring with PFGW which is slow. But this will just be a convenience feature, it probably won't be any faster than MultiSieve, and might be slower.
geoff is offline   Reply With Quote