Fun with Prime Numbers 472
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."
Obligatory (Score:5, Funny)
Re:Obligatory (Score:3, Funny)
Re:Obligatory (Score:5, Funny)
Re:Obligatory (Score:3, Funny)
Re:Obligatory (Score:4, Funny)
Re:Obligatory (Score:4, Funny)
It's true. Good jokes come alomg only so often, and we don't know when.
Re:Obligatory (Score:4, Funny)
Re:Obligatory (Score:3, Funny)
Re:Obligatory (Score:4, Interesting)
Where is it? (Score:4, Funny)
Re:Where is it? (Score:3, Informative)
Re:Where is it? (Score:5, Funny)
Re:Where is it? (Score:3, Funny)
This begs the question: (Score:4, Insightful)
Re:This begs the question: (Score:5, Funny)
Re:This begs the question: (Score:3, Funny)
Re:This begs the question: (Score:4, Insightful)
Re:This begs the question: (Score:5, Informative)
As a matter of fact 2048 bits can represent numbers up to 2^2048 ~= 3.23x10^616. By the Prime Number Theorem [wolfram.com] there is about 2.27x10^613 primes in that space. If each prime required 2048 bits to store, then storing all the 2048 bit primes requires more petabytes then you and I are likely to ever see.
(Jeez I hope I didn't do the math wrong. The most convenient calc I have available to me as I write this in the Windows calc)
Re:This begs the question: (Score:5, Interesting)
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).
Re:This begs the question: (Score:5, Funny)
That function is 92.97% accurate. That's an A-. Good enough for me.
Re:This begs the question: (Score:5, Informative)
Re:A better use? (Score:5, Informative)
Re:A better use? (Score:3, Funny)
Obviously to get a date with a hot chic so you can impress her with the math you know.
Ugliest. Brace. Style. (Score:2, Informative)
What is special about prime numbers? (Score:3, Insightful)
But then again, I haven't studied mathematics to any great extent beyond the multi-var calc and linear algebra back in high school. That was such a long time ago. Any math Geniuses out there want to clue is in on why primes are interesting?
Encryption (Score:5, Interesting)
Re:Encryption (Score:5, Interesting)
In that case I refer you to the fundamental theorum of arithmetic [wikipedia.org], which I think is pretty interesting.
Re:What is special about prime numbers? (Score:2)
Re:What is special about prime numbers? (Score:2)
Re:What is special about prime numbers? (Score:2)
Re:What is special about prime numbers? (Score:2)
Re:What is special about prime numbers? (Score:2, Informative)
Re:What is special about prime numbers? (Score:4, Interesting)
Re:What is special about prime numbers? (Score:5, Interesting)
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 [wolfram.com] article for more details) is of particular interest.
For example, the Riemann Zeta Function [wolfram.com] 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
Re:What is special about prime numbers? (Score:2)
For example, in Z_8, 15*3 = 45 = 5 since the remainder of 45 upon division by the modulus 8 is 5. Strange things can happen in some of these rings. For example, in Z_8 we have 2*4 = 0. Here, 2 and 4 are
Re:What is special about prime numbers? (Score:2, Informative)
Public Key Encryption (Score:3, Informative)
"FUN with Prime Numbers" (Score:2, Funny)
Re:"FUN with Prime Numbers" (Score:2, Funny)
An oxymoron (Score:2)
What manner of masochism is this page peddling in the name of fun?
This can't be good (Score:2, Funny)
Mersenne (Score:2)
Re:Mersenne (Score:3, Informative)
Rather, most of the Mersenne numbers are prime, and most of them are large. That doesn't begin to scratch the surface of most large prime numbers though.
Re:Mersenne (Score:3, Informative)
Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.
Re:Mersenne (Score:3, Informative)
Wrong. There's more than 1.5 million primes up to 24,036,583 (the largest Mersenne exponent known), and only 41 of these are Mersenne exponents.
Read what I typed, then read what you typed.
If I were wrong, then most of the Mersenne numbers would be composite. You have suggested that most of the large prime numbers are not Mersenne numbers, which is an unrelated concept, and substantiates my original post.
Re:Mersenne (Score:3, Informative)
Do you have reading comprehension problems? Or is it just logic that escapes you? If only 41 primes up to 24,036,583 correspond to exponents of Mersenne primes, then the remaining 1.5 million or so primes up to 24,036,583 correspond to exponents of, you guessed it, Mersenne composites. I'd say that a compositeness ratio of 99.997% would indicate that `most' Mersenne numbers are composite.
Re:Mersenne (Score:5, Informative)
Now it seems people here are not familiar with the terminology associated with Mersennes, so I'll give a crash course.
A Mersenne number M_n is of the form 2^n - 1. If 2^n - 1 is prime, then M_n is a Mersenne prime. If 2^n - 1 is composite, then M_n is a Mersenne composite. The integer n in this expression is called the exponent. When I talk about `exponents of Mersenne composites', I'm refering to some prime n for which M_n = 2^n - 1 is composite.
Now if 2^n - 1 is prime, then n must be prime, but the converse is not always true, the smallest counterexample being 2^11 - 1 = 2047 = 23*89. Turns out that for prime exponents n = 24,036,583, only in 41 cases is 2^n - 1 actually prime. A list of these cases can be found here. For the other 1,509,222 prime values of n = 24,036,583, 2^n - 1 is composite. This translates to a compositeness ratio of 99.9973%.
I hope everything is clearer now.
Re:Mersenne (Score:2)
Re:Mersenne (Score:2)
a test (Score:2)
Re:a test (Score:2)
Re:a test (Score:2)
If I don't print or store the primes, I can find all the primes under 2 billion in 2 minutes on my 2.4ghz celeron, since after about 46k all it's doing is reading a bit array of what is and isn't prime. But adding a printf slows it down considerably.
Interesting code (Score:2, Interesting)
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
chosing typesafety over speed? (Score:3, Funny)
I never thought that I'd see a C programmer type something like that.
also doesn't make sense (Score:3, Insightful)
The author isn't a lightweight ... (Score:5, Interesting)
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 [powder2glass.com]
Re:The author isn't a lightweight ... (Score:2)
Fun with slashdotted servers... (Score:2)
Prime Resource (Score:2, Interesting)
Have some more fun with primes (Score:4, Informative)
Of tangential interest is his Goldbach conjecture verification project [ieeta.pt]. You can download his client and contribute to the project. He's shooting for 10^18...
superior algorithm (Score:2, Interesting)
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.
the factor command in Unix/Linux (Score:5, Interesting)
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.
Oh, that works on your friends, on /. on the... (Score:3)
Oh, that works to make your friends think you are a geek.
On
Re:the factor command in Unix/Linux (Score:5, Funny)
Re:the factor command in Unix/Linux (Score:3, Funny)
Not among humans. And they are the only ones with phones.
This is why I'm sharing this with the rest of you so that someone can use it.
Re:the factor command in Unix/Linux (Score:3, Funny)
Re:the factor command in Unix/Linux (Score:3, Informative)
Fat lot of good... (Score:2)
Gaps between primes (Score:5, Interesting)
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.
That's nice, but... (Score:2, Insightful)
The largest known prime is... (Score:2, Informative)
The linked .txt file is 7.1 MB, so it probably will take a while. The Google cache [66.102.7.104] doesn't do the number justice. In fact, the cached number is divisible by 2...
Prime Numbers for cash! (Score:4, Interesting)
Fun with primes? (Score:4, Funny)
First shitting bear post! (Score:3, Interesting)
Improvement (Score:4, Insightful)
Have a look here [utm.edu] for a pretty tight upper bound on the number of primes up to a given number. Using an array, instead of a linked list, would probably lead to a small speed improvement on his code.
He could also use an std::vector from C++. As far as I can tell it's pretty easy to resize.
Prime numbers in bad music... (Score:3, Funny)
Reminds me of... (Score:2, Funny)
I marked up a sweatshirt with a bunch of random prime numbers and, dum roll please, I WAS the 'Indivisible Man'.
Tada.
~tel0p
If you think primes are boring... (Score:2, Informative)
Re:If you think primes are boring... (Score:2)
I think I know what you meant, but I think I like the literal "If you think primes are boring... take a class in abstract algebra" better.
Not as much fun as (Score:5, Funny)
IOCCC (Score:2)
This is actually the MOST important thing to do! (Score:4, Interesting)
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.
Better Implementation (Score:3, Interesting)
Yet Another Prime Program (Score:2)
Here [rsok.com] is my favorite program. It includes a 64-bit version.
my code (Score:2)
I just RTFA... (Score:5, Interesting)
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 [trnicely.net] (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
Re:I just RTFA... (Score:4, Informative)
This raises an interesting question - is it faster to load precomputed blocks from disk or to regenerate it in the L1 cache? One buffer would hold the first block, a second buffer would hold the 2nd-Nth block computed on demand, and a third buffer would hold the target block that's being updated by each successive block.
Re: I just RTFA... (Score:4, Informative)
Working out the mask for those bit operations can take enough time to cancel out the space benefits. I think you could optimize the different masks & their steppings.
I tried this, but I don't know where that program is now. I used 0 as an escape code, allowing me to either note the next delta in hex, or else the current number, to detect errors. I only did this for output, though.
I could see that being effective for the trial factor prime number table, too.
Oh, and the nfsnet thing that's your homepage is cool.
There's a primes program in (uh, on Debian) the bsdgames package; if memory serves, it does the wheel thing suggested.
A suggestion for the article:
If the trial factor prime number table gets big enough to swap (either out of cache, or out to disk), just segment the trial factors too.
This is something I've given a lot of thought to; I've been interested in prime numbers since I was a kid. I've thought about making CDs or DVDs full of primes.
Re:I just RTFA... (Score:3, Informative)
Re:I just RTFA... (Score:4, Informative)
Of course, if you absolutely have to be sure that you're dealing with a prime, you could use a probabilistic algorithm to sieve for probable primes, then apply the n-1 test to obtain a primality certificate for your probable prime (which then becomes a certified prime with 0% probability of being composite). Of course this would be a bit costly, but for small integers the n-1 test is hard to beat -- ECPP and APR-CL have just too much overhead at this range. But I'm pretty sure your application, whatever it is, can live with the small probability that a PrP is composite.
How to prove that all odd numbers are prime (Score:5, Funny)
How to prove that all odd numbers are prime? Well, this problem has different solutions whether you are a:
usage: prime [-nV] [--quiet] [--silent] [--version] [-e script] --catenate --concatenate | c --create | d --diff --compare | r --append | t --list | u --update | x -extract --get [ --atime-preserve ] [ -b, --block-size N ] [ -B, --read-full-blocks ] [ -C, --directory DIR ] [--checkpoint ] [ -f, --file [HOSTNAME:]F ] [ --force-local ] [ -F, --info-script F --new-volume-script F ] [-G, --incremental ] [ -g, --listed-incremental F ] [ -h, --dereference ] [ -i, --ignore-zeros ] [ --ignore-failed-read ] [ -k, --keep-old-files ] [ -K, --starting-file F ] [ -l, --one-file-system ] [ -L, --tape-length N ] [ -m, --modification-time ] [ -M, --multi-volume ] [ -N, --after-date DATE, --newer DATE ] [ -o, --old-archive, --portability ] [ -O, --to-stdout ] [ -p, --same-permissions, --preserve-permissions ] [ -P, --absolute-paths ] [ --preserve ] [ -R, --record-number ] [ [-f script-file] [--expression=script] [--file=script-file] [file...]
prime: you must specify exactly one of the r, c, t, x, or d options
For more information, type "prime --help''
Segmentation fault, Core dumped.
You missed one (Score:3, Funny)
Slashdot:
Re:How to prove that all odd numbers are prime (Score:3, Informative)
Actually, 1 not being a prime is more of a consensus than a mathematical fact.
Primes could be defined so that 1 is also a prime, it's just that way too many theorems we have these days would need to be refined to deal with 1 properly (starting with the fundamental theorem of arithmetics). Which is almost the same as to s
Alternately adding 2 and 4 (Score:3, Interesting)
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
Re:Alternately adding 2 and 4 (Score:3, Informative)
Surf around that site (http://primepages.org/ [primepages.org]), there's lots of good info there.
Re:This begs the question (Score:5, Informative)
Find out more on the Nth Prime Page [utm.edu].
Re:This begs the question (Score:3, Funny)
It consists of a bunch of proofs that there is no largest prime - the list of proofs is entitled "15 good reasons why Pure Mathematics is not taught to first year students." My favourites are:
Proof by example:
"Let x be the largest prime. Then x=91 but 91+6=97 which is prime. Therefore 91 cannot be the largest prime number. Therefore there is no largest prime."
Proof
Re:Fun With... (Score:2)
Re:Complaint about article (Score:3, Insightful)
Re:Variable structure for the lazy? (Score:3, Informative)
http://en.wikipedia.org/wiki/VList
"In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.
Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference.