2009-01-06, 14:38 | #1 |
Aug 2006
1761_{16} Posts |
Sieving for primes
I was considering various ways to sieve for primes (like the Sieve of Eratosthenes), and in analyzing some of the information 'out there' I realized that the key factor is the memory available vs. the high end of the range to be sieved (call it n).
There are algorithms that take essentially linear space (Dunten, Jones, and Sorenson) but sublinear time. These are fast if you're sieving from 1 to some small bound, say a billion. These have been largely replaced by the second category. There are essentially-sqrt algorithms, of which the best is due to the late Atkin: amortized time 1/log log n, space n^(1/2 + eps). This is also useful when starting from 1, but can go considerably further -- limited mostly by processor time. Galway's dissected sieve takes only n^(1/3) space, so it can be used to sieve a relatively small interval starting close to n. The price paid is time: the algorithm runs in linear time. (Galway also has a hybrid sieve conjectured to take only n^(1/4) space at the cost of another log log n factor in time. This could easily go to 10^30, but needs rather a lot of processor time as it requires large intervals to sieve, at least n^(1/2), to achieve even that time bound.) Finally, there are the sieves and fake sieves that require almost no space. Sorenson’s pseudosquare sieve (based on Lukes-Patterson-Williams) is asymptotically as fast as Miller-Rabin, but the primes produced are proven. Further work on enumerating or bounding pseudosquares would be required to make this completely practical, but even at the current state of knowledge it's workable. It can't compete with Atkin-Bernstein or the others for small ranges, but it shines beyond a googol. Space requirement is O((log n)^2). Bernstein's version of AKS is essentially quartic -- (log n)^(4+eps) -- so a theoretical possibility (not practical, ever) would be to test each number with this algorithm and a power detection algorithm. But since only a logarithmic fraction of numbers at a given size are expected to be prime, a cheap test (Miller-Rabin) that can guarantee compositeness in a large fraction of composites can be used. The cheap test is performed on all numbers, and the expensive AKS test is performed on only 1/log n numbers. This makes total performance: (Cost of Miller-Rabin * 1) + (Cost of AKS * 1/log n) = O((log n)^(2+eps)) + O((log n)^(4 + eps) / log n) = O((log n)^(2+eps)) + O((log n)^(3 + eps)) = O((log n)^(3 + eps)) So I was wondering: is there anything important I've left out? Or does anyone want to discuss the complexities I've used? References: A. O. L. Atkin and D. J. Bernstein, “Prime sieves using binary quadratic forms”, Mathematics of Computation 73 (2004), pp. 1023–1030. Daniel J. Bernstein , “Proving primality in essentially quartic expected time”, Mathematics of Computation 76 (2007), pp. 389–403. B. Dunten, J. Jones, and J. Sorenson, “A space-efficient fast prime number sieve”, Information Processing Letters 59:2 (1996) , pp. 79–84. William F. Galway, “Dissecting a sieve to cut its need for space”, Proceedings of the 4th International Symposium on Algorithmic Number Theory (2000), pp. 297–312. William F. Galway, Analytic Computation of the Prime-Counting Function, Ph.D. thesis, University of Illinois. Lukes, R. F.; Patterson, C. D.; and Williams, H. C. "Some Results on Pseudosquares." Math. Comput. 65 (1996), pp. 361–372 and S25-S27. Jonathan P. Sorenson, “The Pseudosquares Prime Sieve”, Lecture Notes in Computer Science, Springer (2006), pp. 193–207. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Distribution of Mersenne primes before and after couples of primes found | emily | Math | 34 | 2017-07-16 18:44 |
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve | mickfrancis | Factoring | 2 | 2016-05-06 08:13 |
sieving primes in arithmetic progressions | maxal | Software | 18 | 2010-10-04 17:11 |
Line sieving vs. lattice sieving | JHansen | NFSNET Discussion | 9 | 2010-06-09 19:25 |
possible primes (real primes & poss.prime products) | troels munkner | Miscellaneous Math | 4 | 2006-06-02 08:35 |