View Single Post
Old 2010-10-02, 21:30   #11
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

186916 Posts
Default

Quote:
Originally Posted by Ken_g6 View Post
Having looked into the math, I'm convinced that Max is correct. (Though he may have gotten that figure from me.)

Although going from one to two k's in sr2sieve doesn't double the runtime, going from two to three should increase the runtime as much as going from one to two did.

Or maybe I'm wrong and Geoff found a better way?
Yes, I got that figure from you. I haven't ever actually looked at the sr*sieve source code myself.

Of course, note that Big-O notation gives only the worst case runtime; often the actual runtime will be lower. I suspect that something of this sort is happening here. From the various large sieves that NPLB's done with sr2sieve, we've empirically determined that there is a significant speed benefit as you add additional k's to a sieve.
mdettweiler is offline