Sieve Benchmark Thread

[amphoria]

Originally Posted by axn

Hmmm... How much time did the sieve take to get to 4e4? 1e6? 10e6?

I am asking because I am "fairly confident" that I can write a custom sieve that can sieve a range of k's to 1e6 (or even 10e6) much faster than NewPGen can. NewPGen isn't really optimised for the initial sieving.

It took 13 hours to get to 4e4. It took about 56 hours to go from 4e4 to 1e6. It is currently still sieving at 27e6 with 4.8M k's remaining (15 hours from 1e6).

By comparison letting NewPGen do the split at p=1e9 took 42.5 hours to 1e9 and another 10.5 hours to go from 1e9 to 100e9.

[amphoria]

Originally Posted by amphoria

It took 13 hours to get to 4e4. It took about 56 hours to go from 4e4 to 1e6. It is currently still sieving at 27e6 with 4.8M k's remaining (15 hours from 1e6).

It took 23.5 hours to go from 1e6 to 1e9.

[axn]

I've got a preliminary sieve cooked up. Currently it sieves a 1T range to 50e6 in around 1.2 hrs (C2D 2 GHz. Linux 64-bit).

Undergoing testing. Once testing checks out, assuming there is interest, I will post the code here.

[Oddball]

Originally Posted by axn

I've got a preliminary sieve cooked up. Currently it sieves a 1T range to 50e6 in around 1.2 hrs (C2D 2 GHz. Linux 64-bit).

Undergoing testing. Once testing checks out, assuming there is interest, I will post the code here.

Wow, that's pretty fast. Were you using one core or both of them?

[Flatlander]

@axn
Brilliant!
I assume someone will be able to port it to Windows, 64 bit?

[axn]

Originally Posted by Oddball

Wow, that's pretty fast. Were you using one core or both of them?

One core.

Originally Posted by Flatlander

@axn
Brilliant!
I assume someone will be able to port it to Windows, 64 bit?

It's written in pascal. Will compile under free pascal (they have 32-bit & 64-bit compilers for windows and linux)

[henryzz]

It looks to me that pascal is not as fast as c++.
http://shootout.alioth.debian.org/u32/pascal.php

[axn]

Originally Posted by henryzz

It looks to me that pascal is not as fast as c++.
http://shootout.alioth.debian.org/u32/pascal.php

I agree, in general. However, the siever spends ~99% of its time in about 15 lines of code which are written in assembly. Even there, I haven't bothered with too much optimization.

The program is simple enough to be ported to any language without much trouble -- but unless you're an assembly expert, you'll find little gain.

EDIT:- More gains can be made from a more complex algorithm. However, the current gains (vis-a-vis Newpgen) are good enough that I can't justify spending more time on performance. My current focus is on increasing the p limit, so that the time spend on sieving by Newpgen is minimized.

[amphoria]

Originally Posted by axn

I've got a preliminary sieve cooked up. Currently it sieves a 1T range to 50e6 in around 1.2 hrs (C2D 2 GHz. Linux 64-bit).

Undergoing testing. Once testing checks out, assuming there is interest, I will post the code here.

Are you sieving for both Twins and Sophie Germains?

[axn]

Originally Posted by amphoria

Are you sieving for both Twins and Sophie Germains?

Yep. Exploiting the fact that k should be multiple of both 3 and 5.

[axn]

Ok. Here's the source code.

Currently sieves 1T upto p=100e6 in 50 minutes. Experiment with tweaking the two parameters in the file.

If you can't download Free Pascal to compile it, I can try compiling for Win64/Linux64 and post the binaries.

EDIT:- Could use more testing. Bug reports welcome.