Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: More Adam vs Hydra Hype

Author: Tord Romstad

Date: 13:37:48 05/26/05

Go up one level in this thread


On May 26, 2005 at 14:18:37, Sune Fischer wrote:

>On May 26, 2005 at 13:15:04, Dann Corbit wrote:
>
>>On May 26, 2005 at 12:02:37, Vincent Diepeveen wrote:
>>[snip]
>>>Hello, i can calculate prime numbers up to 10 million digits at my pc nearly,
>>>though not within 5 minutes.
>>
>>Less than a second, I imagine.

Dann, I think you misunderstood.  Calculating all prime numbers up to 10
million DIGITS is a much more time-consuming task than calculating all
prime numbers below 100 million (8 digits), as I am sure you agree.  :-)

>That's quite an imagination since there aren't any known primes that large :)

You are right.  The largest currently known prime number has 7,816,230 digits.
There are now five known prime numbers with more than one million digits.

>Last I checked only a handful or so had been found with more than a million
>digits, and of course only through weeks of massively parallel super computer
>power.

It's not quite that bad.  The current record prime was found on a single-CPU
P4 2.4 GHz in 50 days.  See the GIMPS ("Great Internet Mersenne Prime Search")
page for details:

http://www.mersenne.org/prime.htm

Note that the world record primes are always Mersenne primes, i.e. prime
numbers of the form 2^p - 1, where p is a prime number.  For numbers of
this form, there exists an extremely fast and simple test for primality,
known as the Lucas-Lehmer test.

Here is a naive implementation of the Lucas-Lehmer test in Common Lisp:

(defun mersenne-prime-p (p)
  "Tests whether 2^P - 1 is a prime, assuming that P is prime."
  (loop with n = (- (expt 2 p) 1)
        for i from 2 to p
        for s = 4 then (mod (- (* s s) 2) n)
        finally (return (= 0 s))))

I compiled this without optimization in Macintosh Common Lisp, a Lisp
implementation which is not known for being particularly fast with
bignum calculations.  Even so, proving that 2^11213 is a prime
(3376 digits) took only 20 seconds on my iMac G5 1.8 GHz.  By
optimizing the code and choosing a compiler with faster bignum
arithmetics it should be easy to push this below one second.

For primes not of the form 2^p - 1, there is no test nearly as powerful
as the Lucas-Lehmer test.  As far as I know, the most efficient known
algorithm is ECPP (elliptic curve primality proving).  Using this test,
proving that a 3000-digit number is a prime would probably take a
few weeks on a modern desktop computer.  Quite a long way from
the 20 seconds used by my simple program above!  By the way,
ECCP and the theory of elliptic curves in general is a really cool
subject, and well worth reading about.

I should also point out that there are probabilistic primality tests
which are much faster.  You can quickly determine that a really
huge number is *almost* certainly a prime.

Finding all primes with less than 10 million digits is of course not
possible within 5 minutes, nor in 5 billion years.  Just consider
how many numbers you have to test, and multiply this number
by the time you need for each primality test, and you will end up
with a length of time which dwarfs the age of the universe.  This
remains true even if we are content to just search for probable
primes.

Tord



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.