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."
This article will be a prime target for bad jokes.
Mom says my
I got a 404...
"I'll have a Guinness, no wait, make that a Coors Light" -Grad student I work with, who shall remain anonymous...
Why not just save primes on a disk instead of recalculating them all the time?
EVER!!!
I understand that number sequences like Fibonacci manifest themselves in Nature and others like pi provide a fairly decent random number generation method. However, aside from the interesting property that they can't be divided by anything other than themselves and 1, I do not 'get' what is interesting or useful about prime numbers.
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?
I find that title so hard to appreciate, maybe I'm just not as big a geek as i thought.
This sounds like one of those topics in high school where if you sounded interested you were written a raincheck for an after school beating by the rugby team.
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
So the macros knock the time down from 4.49 to 4.15 seconds -- less than a 10% reduction. In my opinion, that's not enough benefit to give up the robustness and typechecking of functions.
I never thought that I'd see a C programmer type something like that.
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.
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.
A very fast segmented sieve (to find primes in an arbitrary range) can be found here, by Tomás Oliveira e Silva.
Of tangential interest is his Goldbach conjecture verification project. You can download his client and contribute to the project. He's shooting for 10^18...
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!!!
Find out more on the Nth Prime Page.
Oh, that works to make your friends think you are a geek.
On
The Internet is full. Go Away!!!
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.
Can someone tell me again what the point of this is?
The linked .txt file is 7.1 MB, so it probably will take a while. The Google cache doesn't do the number justice. In fact, the cached number is divisible by 2...
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.
The article feels like it was written for the sole purpose of showing off the author's knowledge. Perhaps I'm just hyper-sensitive to that...
"[A] high IQ is like a Jeep; you will still get stuck, just farther from help!" --Just d' FAQs, c.g.a
How about when you're on the vintage mainframe level in Tron 2.0, ask some random program to calculate the seventh even prime number. When he segfaults, you get access to the directory containing Tron Legacy. Just don't ask yourself that question...
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.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Now, who can forget the Prime Number Shitting Bear?
Have a look here 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.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
encryption.
"It is not how things are in the world that is mystical, but that it exists." -Ludwig Wittgenstein
"One is the loneliest number that you'll ever do Two can be as bad as one, its the loneliest number since the number one"
"Have you ever thought about just turning off the TV, sitting down with your kids, and hitting them?"
My Holloween Costume!
I marked up a sweatshirt with a bunch of random prime numbers and, dum roll please, I WAS the 'Indivisible Man'.
Tada.
~tel0p
take a class in abtract algebra, generally the first class in higher, proof-oriented mathematics. Primes have strong relevance in group theory (which is in itself relevant to quantum mechanics), which leads to rings and fields (widely applicable in linear algebra, analysis), which leads to other advanced topics.
The Prime Number Shitting Bear. Watching a console window spit out prime numbers might do it for the geeks, but everyone can loves 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.
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.
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)
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.
I can only suggest you to heed your own advice.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Excuse my ignorance, but what are extremely large primes used for?
Obviously to get a date with a hot chic so you can impress her with the math you know.
Take the cheese to sickbay, the doctor should see it as soon as possible - B'Elanna Torres, "Learning Curve"
Well, depending on the architecture and the languages, linked lists can be easy :)
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. Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time."
"The underlying structure of a VList can be seen as a singly-linked list of arrays whose sizes decrease geometrically; in its simplest form, the first contains the first half of the elements in the list, the next the first half of the remainder, and so on."
For some reason, the article affirms that the VList is immutable.
Try Corewar @ www.koth.org - rec.games.corewar
I'd venture to say I know what I'm talking about. One can't publish a paper about large-scale distributed primality proofs without knowing these basics. Here's a sample of my work. Now don't get me wrong, I'm not trying to sound like a smart-ass, but I'm not going to let someone question my knowledge in this field (which I have studied for years) and remain quiet.
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.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Shouldn't any decent optimizing compiler (gcc?) inline those commonly-called functions anyway?
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Prime numbers are used in public key encryption. This type of encryption relies on having a function that is easy to generate, but very difficult to reverse. Factorization of large numbers is exactly the function that is used in practice: the prime factors of a large number can easily be multiplied together to get an even larger number, but getting those prime factors back from the giant number is hard. In fact, as the giant number size increases linearly, the time to calculate the factors increases exponentially (using the best known algorithms).
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.
Non-Linux Penguins ?
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 by intuition:
"Prime numbers are integers that can be divided by themselves only; prime numbers are odd with the exception of 2. By intuition as n->infinity, there will always be an odd number cannot be divided by another number besides itself."
Proof by experimental data:
"Suppose n is the highest prime. Then 2n-1 is also prime. But 2n-1>n so there is no highest prime. (Check: 2*2-1=3, 2*3-1=5, 2*5-1=11, 2*11-1=23, so true.)"
But the greatest of them all:
Proof by having no idea what a prime is:
"Say the largest prime is x, then 2x is also a prime since the statement is true for all natural numbers."
Go to http://www.ms.unimelb.edu.au/~paradox/archive/ for the magazine, these proofs appeared in issue 2 of 2002.
If the primary existence of the Earth was as a collective consensus among humans, yes.
You're comparing apples and oranges here. Language does not exist as an objective reality; it relies entirely upon the internal representation of that language shared between its speakers. If in the future nobody understood that language, it would no longer "exist" in any meaningful sense, whereas the Earth exists independently of the internal reality any human (or other being) holds to be true.
In other words, the only way a language can be said to exist is as a "mainstream belief" of its speakers. So, you lose.
Slashdot:
www.eFax.com are spammers
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.