From: Josef 'Jupp' SCHUGT <jupp@...>
Date: 2005-06-25T02:00:38+09:00
Subject: Re: Ruby 6 seconds - on AMD K6 @ 350 MHz (Was: 1. Ruby result:  101 seconds , 2. Java result:9.8 seconds, ...)

Hi!

At Fri, 24 Jun 2005 00:02:42 +0200, Josef 'Jupp' SCHUGT wrote:
> time=Time.now.to_i
> p, f = [ 2 ], 2
> 
> 3.step(50000, 2) do |i|
>   r = Math.sqrt(i).to_i
>   p.each { |f| break if (i%f).zero? or f > r}
>   p.push(i) if (i%f).nonzero?
> end
> puts p
> puts p.length
> puts Time.now.to_i - time

Follows C implementation:

#include <stdio.h>
#include <math.h>

void main(void) {
  unsigned p[25000], f, r, idx = 1;
  int i, j;

  p[0] = 2;

  for (i = 3; i <= 50000; i += 2) {
    r = sqrt(i);
    for (f = p[j = 0]; j < idx; f = p[++j]) {
      if (!(i%f) || f > r) break;
    }
    if (i%f) p[idx++] = i;
  }
  for (f = p[i = 0]; i < idx; i++) printf("%u\n", p[i]);
  printf("%u\n", idx);
}

Runtime (this time estimated using 'time' command):

real: 0.113s
user: 0.064s
sys:  0.009s

I should add that I of course redirect the output to a file, not to
stdout because otherwise I would essentialy measure the terminal's
scroll speed.

The C program almost is a 1:1 equivalent of the Ruby one. I know that
I am wasting memory using "unsigned p[25000]" but I wanted to avoid
the dynamic memory allocation overhead while assuming not to know the
actual number of primes. Obviously 25000 is the upper limit for the
number of primes up to 50000.

Note that the C program could be optimized further (using pointer
arithmetics) but the speedup were that between "fast as hell" and
"ridiculously fast" - pure nonsense.

What does one learn from the speedup? That using prior knowledge can
tremendously improve speed.

In this case the algorithm knowledge is that one need not check if a
number can be divided by any number smaller than it but that it is
sufficient to check divisibility by all primes smaller than its square
root (and that by definition besides 2 no even number can be prime).
The fact knowledge is the list of all primes smaller than the present
candidate for prime.

Note that it is not a must to collect all primes! To find all primes
up to 50000 one only needs to store all primes smaller than 223 - the
integer part of square root of 50000. I store all of them because in
this case memory is not a problem and adding checks would slow down
the programs.
Josef 'Jupp' SCHUGT
-- 
Preposition: Microsoft uses Power PC CPUs for their Xbox while Apple
uses Intel CPUs for their Mac.
Theorem: Hell has been invaded by flyng pigs, then frozen.
Proof: Uncertainty drive manual, appendix A, 42nd edition or later.