 What Is: World's Largest Known Prime Number |
|
|
|
|
  |
  Mar 16 2005, 04:35 AM
Post
#1
|
|
|
PsYcheDeLiC dR3aMeR  Group: Admin Posts: 2,242 Joined: 29-January 05 From: Nakorn Chaisri, Thailand Member No.: 2,411  |
Hi all,
[/tab] I just came across this while searching for some mathematical principles. Do you know that there's this foundation named Great Internet Mersenne Prime Search (GIMPS) whose sole work is to search for the largest prime number known to man ? Every couple of years they come up with a new number only to beat their earlier score. The last one found and the largest currently known prime, 2^24036583 – 1, was found by Josh Findley through the GIMPS project on May 15, 2004. It is 7,235,733 digits long, almost one million digits more than the previous record holder. Here's a direct quote from the InfoPlease.Com site: QUOTE Euclid proved in the 3rd century BC that there are an infinite number of prime numbers. A prime number can be divided only by itself and the number 1. Primes serve as the building blocks for all positive integers, and have applications in cryptography and other fields. Mersenne numbers are numbers that are one less than a power of two (2^n – 1). A Mersenne number that is also a prime number is called a Mersenne prime. These can be found and verified relatively quickly. Before 1952, 12 Mersenne primes were known; with the aid of computers, 29 more have been found. The seven largest have all been found by the Great Internet Mersenne Prime Search (GIMPS), a distributed network of volunteers using their spare computer power to find the largest Mersenne primes. The largest currently known prime, 2^24036583 – 1, was found by Josh Findley through the GIMPS project on May 15, 2004. It is 7,235,733 digits long, almost one million digits more than the previous record holder. The Electronic Frontier Foundation is offering a $100,000 award to whomever is the first to find a prime number with at least ten million digits; it seems likely that this will be claimed within the next few years. [tab]As you can see there's a very lucrative prize waiting for you if YOU happen to be the one with the new Prime in the block.  Read more about it at: 1. http://www.infoplease.com/ipa/A0920820.html 2. http://news.bbc.co.uk/1/hi/sci/tech/1693364.stm 3. http://www.mersenne.org/prime.htm |
 |
 
|
|
Mar 16 2005, 10:18 AM
Post
#2
|
|
|
Way Out Of Control - You need a life :)  Group: Members Posts: 1,366 Joined: 14-September 04 From: Nottingham England Member No.: 570 |
Great...
So all i need now, is several hundred old computers, use OpenMOSIX to constuct a cluster computer, and getmyself that 100,000 that with any luck, might just about ocver my electricity bill. |
|
|
|
|
Mar 16 2005, 01:22 PM
Post
#3
|
|
|
PsYcheDeLiC dR3aMeR Group: Admin Posts: 2,242 Joined: 29-January 05 From: Nakorn Chaisri, Thailand Member No.: 2,411 |
Hehehe... it won't take that much. Just make a cluster of the brand new p4's or alikes (10 would be good I guess) and be out on the hunt... I wonder though what kind of equipment it takes to perform such intense number crunching operations (other than supercomps of course).. Do you know of any site that guides you or at least provides the basic specs for such a job ?? It's worth a try - $100,000 is no mean joke - though no conventional Data Type can handle those numbers. So you got to come up with your own code capable of handling 32-64-128 (whatever) bit integers in order to deal with such immense numbers.
|
|
|
|
|
Mar 16 2005, 01:37 PM
Post
#4
|
|
|
Way Out Of Control - You need a life :) Group: Members Posts: 1,366 Joined: 14-September 04 From: Nottingham England Member No.: 570 |
There are libraries in C which are designed to allow you to use data types of any length. for example you could define a float data type that uses 1000 bytes, then use it to divide 10 by 3.
but these large data types have to be calculated by an emulated cpu that wil not approximate divisions like x86's do, which is slower. I think a cluster computer would be perfect for this type of number crunching. Because the search can easily be forked() into simultanius porcesses that do not need to compunicate to function. to stand a good chance of winning, you would need to clock up more computing power for hours than all the other ocntestants put together, i dont think 100 p4's would do it 
|
|
|
|
|
Mar 16 2005, 01:47 PM
Post
#5
|
|
|
PsYcheDeLiC dR3aMeR Group: Admin Posts: 2,242 Joined: 29-January 05 From: Nakorn Chaisri, Thailand Member No.: 2,411 |
100 P4s - you'd get one for approx. THB 22, 000 here.. that's about $550 - times 100 = $55,000 ... yeah you're quite right - just the hardware setup alone (include a couple of extremely high performance switches)..would go way way above the prize money.. How about the concept of distributed internet computing - that might cut down the setup cost - but then you've to depend of ppl volunteering and downloading your client.. lot of hassle. Hrrrrmmmppphhh.. What wouldn't I give to have a setup like that though.
|
|
|
|
|
Mar 16 2005, 04:33 PM
Post
#6
|
|
|
Way Out Of Control - You need a life :) Group: Members Posts: 1,366 Joined: 14-September 04 From: Nottingham England Member No.: 570 |
QUOTE How about the concept of distributed internet computing lol, yea thats what they are doing. by downloading and running their software, you are voulenteering your spare cpu power. but the cash goes to the machine that made the discovery. so although its a joint effort the prize money is trying to encourage you to volenteer as much computing power as possable to increace your chances of winning. |
|
|
|
|
Mar 20 2005, 01:05 PM
Post
#7
|
|
|
Premium Member Group: Members Posts: 311 Joined: 1-November 04 Member No.: 1,290 |
Doesn't anyone have a formula for working out the pattern of the prime numbers?!
If someone could find that then we wouldnt have this problem. |
|
|
|
|
Mar 21 2005, 05:52 AM
Post
#8
|
|
|
PsYcheDeLiC dR3aMeR Group: Admin Posts: 2,242 Joined: 29-January 05 From: Nakorn Chaisri, Thailand Member No.: 2,411 |
I'm sure there are such formula's in existance. The simplest approach would be to apply the rules of divisibility on each successive integer from the set of whole numbers. The main problem is that for any integer 'n' you've to check whether it's divisible by any of the numbers: 2...(n-1) ... Here's an routine written in VB that generates an array of primes till a number 'n' that you specify.... Get it Here.
But if you study the routine a little bit, you'll notice how fast we'll run out of stack/memory space as we go for higher and higher numbers. The standard integer/double data types aren't sufficient at all - in such a case you'll have to create your own high capacity data types to hold these humongous primes. As qwiji pointed out there are some C based libraries that aid you in designing such data types, but you'll need to be fairly advanced in Mathematics to be able to makes sense of them in any way
|
|
|
|
|
Mar 21 2005, 09:46 AM
Post
#9
|
|
|
Member [ Level 2 ] Group: Members Posts: 66 Joined: 28-December 04 From: Los Angeles, CA Member No.: 1,896 |
Wow, that's pretty interesting. It's a good thing that the largest prime number happens to be a Mersenne Prime, otherwise it would be so long you couldn't even write it down.
|
|
|
|
|
Mar 23 2005, 06:47 PM
Post
#10
|
|
|
Penguin Holmes Group: Members Posts: 225 Joined: 22-March 05 From: Poland Member No.: 3,163 |
Hi... what I know from my "theoretical math" study, the most efficent way to find prime numbers is Sieve of Eratosthenes. It gives you chance to get them counted very fast, and memeory usage is one bit per prime number, so this can be it... I will post there small code (maybe wrong, couse i'm mathematician, but I tested it with gcc... remember add math library when compiling, you should also add optimalistation - like this:
gcc -O2 test.c -o test.o -lm this method works fine and result of: time test.o is something about 0.001 ms for all prime numbers from 0 to 100000 - this is limit of this example and my coding knowledge ), I can give you some rules and theory, so if know some language, you would be for sure able to build it yourself... so let's start:First of all we are generating methods to store information, we are using table of long long integer, since we need many bits with possible less indexes (in example I used char...), and creating few functions that will put 0 or 1 to bit represented by number (prime, or not prime) and read value of bit that represents it, then we need to put that values: number 0 - value 0 number 1 - value 0 other - as far as we can - value 1 when we have this ready, the main generating function... we are taking first number that have value of 1, but is before sqrt of largest possible number, lets call it p like prime and we are putting 0 to all numbers that looks like a*p, where a=2,3,4,... till end of all numbers, then we are taking first number that have value of 1... this is how you can do it with C: CODE // program 3.06 - Erasto // by Giniu #include <stdio.h> #include <math.h> #define SIZE 1000000 char erasto[(int)(SIZE/8)]; void putErasto(int number) { int position, inside; char value; position=number/8; inside=number%8; value=(1 << inside); erasto[position]|=value; } void delErasto(int number) { int position, inside; char value; position=number/8; inside=number%8; value=~(1 << inside); erasto[position]&=value; } char checkErasto(int number) { int position, inside; char value; position=number/8; inside=number%8; value=(1 << inside); if ((erasto[position]&value)!=0) { return 1; } else { return 0; } } void clearErasto(void) { int flow; for (flow=2; flow<=SIZE; flow++) { putErasto(flow); } delErasto(0); delErasto(1); } void countErasto(void) { int flow1, flow2, countTo; clearErasto(); countTo=sqrt(SIZE); flow1=2; while (flow1<=countTo) { flow2=flow1*2; while (flow2<=SIZE) { delErasto(flow2); flow2+=flow1; } flow1++; while ((flow1<=countTo)&&(checkErasto(flow1)==0)) { flow1++; } } } char isPrime(int number) { return !checkErasto(number); } int main(void) { countErasto(); //there what you need... just like: printf("\n\n 123123 is"); if (isPrime(123123)) printf("n't"); printf(" prime number,\n"); printf(" but 7 is"); if (isPrime(7)) printf("n't"); printf(" prime number.\n\n"); } This maybe isn't best example, but how I said I'm mathematician not a coder, so this is only viewing of an idea... I tried as much as I could... just try it and remember - it always takes same time - to generate sieve of given size... hope this will help  Giniu edit----------------- oh, and this example was made on "introduction to math in algorythmic", thats why 3.6 - list 3 exercise 6 - havent time to change this... and: "You can copy and do with it whatever you want, as long as you left line: // by Giniu at top of this, you can add something like orginal version or whatever... I don't realy care... just left autor...
|
|
|
|
|
Similar Topics
|
Lo-Fi Version | Time is now: 30th August 2008 - 05:05 PM |