Re: little isprime challenge

On 2005-08-23, Bart Vandewoestyne <MyFirstName.MyLastName@xxxxxxxxxx> wrote:
> I know there has been a kind of `string-challenge' in this group
> which I have not been following... but it's been taking a while
> and from what I've read I have the feeling that some people got
> bored of it and now are definitely in need for something else...
> so I have another little `isprime-challlenge' :-)
>
> It's just 100% pure for the fun of it, and maybe it will also
> teach some more novices and `less experienced' young fortran
> programmers as me good optimization skills. It might also be usefull for
> some people in need for some prime routines.

OK. The little isprime challenge has come to an end. My final testprogram is
at http://www.cs.kuleuven.ac.be/~bartv/stuff/time_isprime.f95

These are the timing results on my computer:

bartv@archimedes:~/fortran$ make time_isprime
F -o time_isprime -O4 time_isprime.f95

bartv@archimedes:~/fortran$ ./time_isprime
How many numbers should be tested? 1000000
What method (from_1|from_huge) ? from_1
from_1: Brooks's method found 78498 primes in 0.15 seconds.
from_1: Fermat's method found 78498 primes in 0.74 seconds.
from_1: Elliot's method found 78498 primes in 0.56 seconds.
from_1: Rich's method found 78498 primes in 0.61 seconds.
from_1: Bart's method found 78498 primes in 1.08 seconds.

How many numbers should be tested? 1000000
What method (from_1|from_huge) ? from_huge
from_huge: Brooks's method found 46602 primes in 66.60 seconds.
from_huge: Fermat's method found 46602 primes in 1.08 seconds.
from_huge: Elliot's method found 46602 primes in 69.20 seconds.
from_huge: Rich's method found 46602 primes in 21.62 seconds.
from_huge: Bart's method found 46602 primes in 98.68 seconds.


I'll leave it to the reader to decide which version is preferable. What I
have learned from this challenge is the following:

* First of all, look for a fast theoretical algorithm :-)
* The loop-unrolling-alike technique as it is used by Brooks can speedup
dramatically
* I wonder if Fermat's method suffers from overflow problems since we are
testing up until huge(n)-1 and this algorithm requires 8-byte integers...
that would maybe explain the speed of the method, but apparently, it finds
as much primes as the other ones so it seems correct? I haven't looked at
the value of the primes yet, but this could be something for further
investigation... :-)

If I had to choose, I think I would go for Elliot's method because it doesn't
require 8-byte integers and it is definitely more readable than Brooks's method ;-)

See you in the next challenge (coming soon... :-)!
Bart

--
"Share what you know. Learn what you don't."
.

Relevant Pages

  • Re: Switching to Linux, now what to buy?
    ... > notice that the peaks in the phi function WERE the sequence given. ... of intelligence tests and quizes, ... Toward the end I began critizicing my work, feeling that the sets ... suggested inclusion of knowledge about primes as something ...
    (comp.os.linux.setup)
  • Re: Proving primality of an integer
    ... > how about you give the timing for large primes (100's of digits of ... > the size of rsa primes). ...
    (sci.crypt)