Slashdot Mirror
Fun with Prime Numbers
Steve Litt writes "Fun
With Prime Numbers contains a series of prime number finding algorithms starting with the most brute force imaginable, and working up to a paged algorithm capable of finding the first 1,716,050,469 primes in an hour and a half on a commodity machine. There are faster algorithms on the net, but these algorithms are within the reach of mere mortals and are fully explained."
Reminds me, here's code to generate prime numbers: (earlier thread)
http://www.de.ioccc.org/2004/vik2.c
to cheat: http://www.de.ioccc.org/2004/vik2.hint
I didn't link them on purpose
BTW, the first bazillion prime numbers HAVE been calculated, so for those /.'ers with spare CPU cycles, consider something perhaps more worthwhile such as Folding@HOME
Hulk SMASH Celiac Disease
Read Penn Jillette's great explanation for details.
Vino, gyno, and techno -Bruce Sterling
Here's a nice, fun little resource for those interested in prime numbers. Actually, it's pretty large and exhaustive: The Prime Pages. Make sure to check out Prime Curios!; fascinating stuff.
djb:
see http://cr.yp.to/primegen.html
primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
primegen can generate primes up to 1000000000000000, although it is not optimized for primes past 32 bits. It uses the Sieve of Atkin instead of the traditional Sieve of Eratosthenes.
There is a command in many unices and Linux called factor.
If you want to be a true geek you can try it on your friends phone numbers and find out if it is a prime.
Then, the next time you talk, inform them that their phone number is a prime, or tell them of their phone numbers prime factorization, and enjoy watching them think that you are a super geek and a super genius.
For even better effect, pretend to count in your head before you tell them this.
The Internet is full. Go Away!!!
Brief overview. There is also the Prime Spiral.
From the article:
... * 65537 + 2 = 2 * (3 * ... * 65537 + 1) ... * 65537 + 3 = 3 * (2* 4 * ... * 65537 + 1)
...
... * 65536 * 65537 + 65537 = 65537(65536!+1)
..., 65537! + 65537 are all nonprime (the first is divisible by 2, the second by 3, the thrid by 4 etc). Since we also know that there are infinitely many primes, there must be a prime greater than 65537! + 65537. The biggest prime less than 65537! + 2 and the least prime bigger than 65537! + 65537 are consecutive primes which are at least 65536 apart.
..., 6! + 5} ={722, 723, 724, 725, 726} are all nonprime, but also 24, 25, 26, 27, 28 are 5 consecutive nonprime numbers.
who can be sure that there aren't two consecutive primes somewhere that are more than 65536 apart
Let's recall elementary number theory:
65537! + 2 = 2 * 3 *
65537! + 3 = 2 * 3 *
65537! + 65537 = 2* 3 *
So the 65536 consecutive numbers 65537! +2 ,
Of course, 65537! is a massive number, which is unlikely to crop up in these calculations. There may be other sufficiently large gaps between primes among smaller numbers.
Consider, for instance, the method above applied with 5 in the place of 65536. We see that {6! +2,
For where we can expect large 'prime-free' gaps, I'll defer to any number theorist.
If you're interested in running a distributed.net-like application with the chance to make some money using your CPU cycles to help find prime numbers, have a look at here. They give some good information about what prime numbers are, and what they're good for.
BeauHD. Worst editor since kdawson.
I do not 'get' what is interesting or useful about prime numbers.
...)= ((1-2^(-2))*(1-3^(-2))*(1-5^(-2))...)
There is therefore a connection between pi and the distribution of the primes. Math is crazy stuff.
Prime numbers are useful in encyption, but those are very large primes that are difficult to factor. To a mathematician, prime numbers are fascinating. The distribution of primes, which is specifially random but generally predictable (check out the MathWorld article for more details) is of particular interest.
For example, the Riemann Zeta Function of n, which is the infinite sum of all terms k^(-n)[k varies from one to infinity], is expressable as the infinite product (1-p1^(-n))*(1-p2^(-n))*(1-p3^(-n))... [where pn is the nth prime number]. This is a mind-boggling connection. For example Zeta(2)= (pi^2)/6 = (1 + 1/2 + 1/4 +1/8
I'm dating myself, but this reminds me of a computer science class (late 80s) where we used the Sieve of Eratosthenes to find primes. Had fun writing it on a VAX 8550 and then porting it to our lightning fast 80286 10MHz PCs...
s .h tml
http://mathworld.wolfram.com/SieveofEratosthene
0x1337 is prime
Now, who can forget the Prime Number Shitting Bear?
For those who scoff at this kind of stuff, we have to keep in mind that it's this sort of tinkering that results in some of the most amazingly useful and interesting stuff later.
I have one lament, which is that his code formatting (indenting) got munged, making it really hard to read the code. I'm really tired, so I just couldn't manage to read through all the C code. I hope he fixes the page so that I can read it more easily later.
As mentioned, DJB's primegen is much faster. Even his Sieve of Eratosthenes implementation will do the primes up to a billion in 1.38 seconds on a 2.4 GHz P4, which is roughly 100x faster than this guy's "all primes below 100 million in less than 13 seconds" (although he doesn't specify on what machine). There's no reason to be using huge memory "pages," you can sieve up to N with any size interval you want (like say, the size of your L1 d-cache) using only Sqrt(N) memory for the primes up to Sqrt(N).
...and I'm going to list a few improvements here that I think the author missed.
In one of the early programs, the author had the idea of skipping all even numbers, which are of course divisible by 2. In the next program he found out how he could skip numbers divisible by 3. One can make a systematic method out of that -- in the literature it's known as adding a wheel to the sieve of Erathostenes. Thing is, he implemented the sieve of Erathostenes foregoing this improvement he had implemented earlier. This leads to a big improvement: when using a wheel with the first four primes 2,3,5,7, there are only 48 residue classes out of 210 = 2*3*5*7 possible that are not divisible by any of these four primes. In practice this means that, for each 210 numbers you'd consider, the sieve would only need be applied in 48 of them. That's a gain of 4.375. One can make a gain of nearly 5 using a wheel of the first five primes, but it begins to get complicated.
Another improvement would be to make the program cache-friendly. He sort of did this, down one level of the memory hierarchy, by paging the data to disk -- now he only needed to realize that, just as memory is much faster than disk, cache memory is faster than main memory. I've developed a sieve employing this optimization and it pays off indeed. This is considered a basic technique in the realm of high-performance computing. (The NFSNET, see my sig, uses a sieve including this and other optimizations, for instance).
I might get flamed for this, but he should consider assembly programming. There aren't many applications where assembly will pay off so handsomely as this one, and the `core' of the sieve is very small, so only a few lines of assembly are needed. Vector integer instructions, such as MMX and the integer instructions of SSE2, can be employed to very good advantage here. My sieve program also included this, and it gives a real nice boost -- and only about 25 lines of assembly were used, the rest was C.
Lastly there's the issue of representing the output. He stored the primes on disk by writing their values. A little compression can be realized in this representation: for instance he's printing out the primes in decimal, while hexadecimal would be more space-efficient. And instead of printing out the ASCII characters from 0 to 9, A to F, he could use a binary representation and read them through an hex dump -- that saves half the space, as a byte is used to store two hexadecimal digits instead of one.
A perfectly good representation that could save a lot of space (8 times, to be precise) would be a bitmap, which he used on some of his programs. That's where you represent primality or lack of it by setting and clearing bits of an integer. It's pretty easy to determine a prime from a bitmap value, so this representation is just as good as the previous one. One could also use the wheel idea I explained before to save even more space: a concrete example would be that for each block of 210 numbers, one needs only bitmaps for 48 of them, as the rest are divisible by the first four primes. In this example a savings of 4.375 would be realized. Of course, all these ideas would require special readers programs, instead of just opening up the files in a text editor -- a small price to pay for such a large space savings.
But in case only sequential reading of the primes is desired, there is an even more efficient representation: just write out the prime gaps, i.e. the difference between consecutive primes. One bit can be saved by realizing that, other than 3 - 2, all prime gaps are even, so one can just store the prime gap divided by two. One could really nitpick and point out that 0 is an impossible prime gap, so one could subtract two from all gaps, but this gain is too small to be worth the hassle. According to Thomas Nicely (incidentally the guy who discovered the bug on the Pentium FPU during his studies on computational number theory), one could store the prime gaps of all
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
First, what's with the %ull format specifier in sprintf - is that even a valid format specifier?
Next, why subtract 2 from your buffer length when printing?
Finally, why bother with the "printprime" and sprintf function altogether - is there anything wrong with:Okay, this is kind of nitpicking, but I'm clearly missing something obvious here...
- Any Day above Ground is a good Day (Michael Rich, 1997)
Indeed, the number of particles in the universe is assumed to be approximately 10^85, so if you would store one bit per particle, you'd need about 5*10^530 universes to store all those primes. Hell, even if you stored at every single particle as many bits as there are particles in the universe, you'd still need 5*10^445 universes.
:-)
Of course that's assuming you stupidly write all those numbers individually down, using the whole 2048 bitf or each number. Now what if we compress the table?
The complete list can, of course, be stored in a bitfield with 2^2048 individual bits which tell if a given number is prime or not (e.g. 1 means the number is prime, 0 means it's not). Now, of those 3.23*10^616 bits, about 2.27*10^613 bits are 1. So a simple approximation would be to treat the bits as independent, with each one having a probability of (2.27*10^613)/(3.23*10^616)=7.03*10^-4 of being 1. So if we neglect all correlations of the bits, we get an information of about 0.0084 bits per bitfield bit, which means we can compress to about 2.7*10^614 bits. That is, even neglecting all correlations (even the trivial ones of all even numbers except 2 being non-prime) we get only about 12 bits per prime. That's substantially less than the 2048 bits per prime we'd need with straightforward storage. Of course, we would still need an insane number of universes to store our table
Now, of course we know that we can "compress" the full table very well to a small prime-finding program which fits nicely on even a single floppy (but would take longer to "decompress" than we are willing to wait), so the list of primes doesn't actually contain too much information (indeed, the program can compress the whole infinite prime table - decompression of course needs unlimited ressources, then -, therefore the average information content of a single prime is obviously zero).
The Tao of math: The numbers you can count are not the real numbers.
This was the method I used in my first attempt to write a prime-number generator. I figured that any positive integer can be written as 6n, 6n+1, 6n+2, 6n+3, 6n+4 or 6n+5 where n is an integer; and furthermore, 6n, 6n+2 and 6n+4 are definitely even, while 6n+3 is definitely a multiple of three. So we only need to try 6n+1 and 6n+5 to see if they are primes. Also, the smallest prime factor of a non-prime number must be smaller than or equal to its square root; so you don't need to try every known prime for divisibility. Rather than do a square root, though, I squared the testing_factor and compared it with the prime_candidate. This is quicker for small prime_candidates; but, as the list of known primes {and thus testing_factors} grows, eventually the many multiplications will start to take longer than one square root evaluation. The crossover point actually is a system-by-system variable, since it depends on FPU performance.
..... } can be used, with very slight modification, as a sort of pre-sieve to eliminate things that are never going to be primes. For instance, looking at 30n+m, the "potential primes" are 30n+1, 30n+7, 30n+11, 30n+13, 30n+17, 30n+19, 30n+23 and 30n+29. {The primes smaller than 30 are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29; see how we simply have excluded everything which is a factor of 30, and included 1.} This list is good up to and including 209 {210 = 2 * 3 * 5 * 7} beyond which a new list will apply going something like 210n+1, 210n+11, 210n+13 ..... }
..... I think I might have to go and investigate .....
I subsequently worked out that any list of primes stopping one shy of a product of primes-so-far {6, 30, 210, 2310
Now this is beginning to look like a recursive process! Mind, we're getting longer and longer lists as the density of primes is getting smaller. Hmm
Je fume. Tu fumes. Nous fûmes!
Yves Gallot's GFN (generalised Fermat Number) search, and my GEFN (generalised Eisenstein Fermat Number) search, are both as efficient when it comes to the primality tests. If anything, our tests might be more efficient, as our DWTs are simpler than Mersenne's IBDWT. Both of our forms are definitely more efficient than Mersennes, as we can _presieve_ ours to massively reduce the number of lengthy tests that we need to do.
The only reason GIMPS (great internet mersenne prime search) has the top ?4 primes at the moment is because they have 1000x as much CPU power as Yves' GFN search, and 10000x as much CPU as my GEFN search.
With Percival's generalised DWT algorithm, those searching for Proth/Riesel forms (k*2^n+/-1) with very small k also have a similarly efficient primality tests.
The age of Mersennes is only not over yet because of the fact that they have such a head start. They will be caught up with over time when other projects get similar quantities of CPU power.
FP.
Also FatPhil on SoylentNews, id 863
There are a couple of easy improvements that can be made to Mr. Litt's program that I haven't seen mentioned.
When removing multiples of a new prime p, you don't need to test the even multiples of p, 2 already did that for you. This cuts your work in half.
Although less asymptotically beneficial, you can start with p^2 since the lower multiples of p have already been done in previous passes.