User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 November 6th, 2008, 08:13 AM #1 Global Moderator   Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Listing primes: a personal history I've been writing program to enumerate primes since grade school. I thought that a description of the various algorithms I used might be instructive... or at least give you a chance to laugh at me. I hope this will be useful for cknapp, afreude, and anyone who wanders by. 1. Worse Than You Thought Possible: O(n^2) I read the definition of prime numbers and wrote a program directly from it. For each n in the range I was testing, I counted the number of divisors. If it was exactly two, I printed the number. At least the memory use was constant! A non-improvement I made to the program was to test from 2 to n-1 and set a flag if a number divided n. 2. Really bad (but better): O(n^2/log n) Just like the above, but terminating early if it found a factor. Each composite took time O(sqrt(n)), while each prime took time O(n), for a total of O(sqrt(n) * n + n * n/log n) = O(n^1.5 + n^2/log n) = O(n^2/log n). 3. A vast improvement: O(n^1.5) I wish I could say that I invented this method, but in fact I read the idea. It immediately made sense, and cut the time for checking primes dramatically. Memory use was still constant, but the time speedup was so dramatic that I could generate primes faster than I could print them (to a printer). I did realize on my own that I could further improve this by checking only odd numbers and odd divisors. This doubled the speed, but gave no asymptotic improvement. I also saw that I could further improve the process (by wheel sieving, but I didn't know the term), but wasn't sure how to program it. I did see that each larger wheel would take more and more programming effort with diminishing return. I guessed that this was probably the best method, up to improvements by some small constant. (This was around 8th grade, forgive my naivete.) 4. Trial division: O(n^1.5/log n) Wheel sieving is great, but wouldn't it be better to check divisibility by only primes? Not realizing the huge gap between N and sqrt(N), I originally thought this would be impractical. But trying it out I found this to be a further small improvement. But I paid for it in space, going from constant to O(sqrt(n)/log n). 5. Sieve of Eratosthenes: O(n log n) What if you checked the whole list for primality at the same time, instead of going one-by-one? You could avoid doing divisions entirely, relying on the fact that if p|a, p|(a+p). You make a list as long as the number of primes you're going to check, marking all but the first as provisionally prime. For each prime p less than sqrt(N), mark 2p, 3p, ... as composite. When you're done, all remaining provisionally prime numbers are, in fact, prime. The memory use is large, though: since you hold a list as long as the interval itself, it takes O(n) memory. Suddenly, space is more of a limiting factor than time! 6. Segmented SoE: O(n log n) By splitting the list into many small segments (perhaps as many as sqrt(N) segments with lengths as small as sqrt(N)) the memory use can be cut down to O(sqrt(n)). This is the first step back on the list, as it actually takes more time than the previous method. Although the asymptotic complexity is no worse, the big-O constant holds a lot of extra work determining where to start sieving on each piece. 7. Sieve of Atkin: O(n) The sieve of Atkin is a much more difficult sieve to implement than the sieve of Eratosthenes. Instead of checking for the linear form n = a * b, it checks for various quadratic forms depending on the value of n mod 12. I had a working version of this sieve some time ago, though unfortunately I may have lost it. The careful programming necessary to make this form competitive is tricky; my version was really no better than the SoE for normal sizes. Other fun sieves: Galway's dissected and hybrid sieves (the latter can be considered experimental) and the LPW-Sorenson pseudosquare sieve. These sieves are good for enumerating small numbers of large primes, perhaps all primes between 10^20 and 10^20 + 10^9. They cannot compete with the Sieve of Atkin on speed, though, only on space. Note: Complexities reported here are (1) arithmetic complexity, not bit complexity, and (2) my calculations. They may not match other reported values, either because my algorithm is not the same or because the other uses bit complexity. The sieve of Atkin, for example, is usually described as sublinear -- O(n/log log n) -- because of a scaling wheel sieve built in and other such tricks. But a practical implementation does not vary the size of the wheel, so the true complexity is often linear. (Not that I should complain, it's quite fast regardless!) Tags history, listing, personal, primes Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post CherryPi Calculus 2 April 18th, 2012 04:19 AM Flook Real Analysis 1 January 22nd, 2012 03:54 AM htamevolI Advanced Statistics 0 November 16th, 2010 12:35 PM The Chaz New Users 8 September 10th, 2010 04:38 AM approx Number Theory 6 February 24th, 2009 06:10 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.       