1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

Ruby:

def is_prime(number)
for i in 2..(number-1)
if number%i==0 then return false
end
        end
return true
end
######### star here:How many primes in 2 to 50000?
max_number=50000
start_number=2
total=0
time=Time.now.to_i
for i in start_number..max_number
if is_prime(i)
#puts i
total+=1
end
end
time=Time.now.to_i-time
puts "There are #{total} primes between #{start_number} and #{max_number}"
puts "Time taken #{time} seconds"

Java :
import java.io.*;
class prime
{
   private static boolean isPrime(long i)
   {
       for(long test = 2; test < i; test++)
       {
     if((i%test) == 0)
     {
    return false;
     }
       }
       return true;
   }
   public static void main(String[] args) throws IOException
   {
       long start_time = System.currentTimeMillis();
       long n_loops = 50000;
       long n_primes = 0;
       for(long i = 2; i <= n_loops; i++)
       {
     if(isPrime(i))
           {
         n_primes++;
           }
       }
   
       long end_time = System.currentTimeMillis();
       System.out.println(n_primes + " primes found");
       System.out.println("Time taken = " + (end_time - start_time)+ "millseconds");
   }
}

Perl:

######### star here:How many primes in 2 to 50000?

# start timer

$start = time();

$max_number=50000;

$start_number=2;

$total=0;

for ($ii=$start_number;$ii<=$max_number;$ii++){

if (&is_prime($ii)==1)

{$total+=1}

}

# end timer

$end = time();

# report

print "There are ",$total," primes between ",$start_number," and ",$max_number,"\n";

print "Time taken was ", ($end - $start), " seconds";

sub is_prime() {

my ($number) = $_[0];

my ($si)=2;

for ($si;$si<$number;$si++){

if ($number % $si == 0) {

return 0;}

}

return 1

}

···

---------------------------------
Discover Yahoo!
Find restaurants, movies, travel & more fun for the weekend. Check it out!

Well, Ruby is a scripting language and not compiled, so its
results in the ballpark of Perl is about right. Only 10x
as slow as Java JVM? wow, that's pretty good, Ruby rocks!

Also, for more fun, run your Ruby through YARV and also
run zenoptimize on it

Benchmarks are great fun and prove nothing.

Ralph "PJPizza" Siegler

···

On Wed, Jun 22, 2005 at 04:55:58AM +0900, Michael Tan wrote:

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

Yeah, Ruby is always going to be slower than java, since java is semi-compiled, whereas Ruby is interpreted from scratch. As for your algorithm, it is sufficient to change your is_prime methods from:

for i in 2...number

to

for i in 2..Math.sqrt(number).to_i

Which will significantly reduce the number of tests you will perform.

David

Michael Tan wrote:

···

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal? 1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

Ruby:
def is_prime(number)
for i in 2..(number-1)
if number%i==0 then return false
end
        end
return true
end
######### star here:How many primes in 2 to 50000? max_number=50000
start_number=2
total=0
time=Time.now.to_i
for i in start_number..max_number
if is_prime(i) #puts i
total+=1
end
time=Time.now.to_i-time
puts "There are #{total} primes between #{start_number} and #{max_number}"
puts "Time taken #{time} seconds"

Java :
import java.io.*;
class prime {
   private static boolean isPrime(long i)
   {
       for(long test = 2; test < i; test++)
       {
     if((i%test) == 0)
     {
    return false;
     }
       } return true;
   }
   public static void main(String args) throws IOException {
       long start_time = System.currentTimeMillis();
       long n_loops = 50000;
       long n_primes = 0;
       for(long i = 2; i <= n_loops; i++)
       {
     if(isPrime(i))
           {
         n_primes++;
           }
       }
          long end_time = System.currentTimeMillis();
       System.out.println(n_primes + " primes found"); System.out.println("Time taken = " + (end_time - start_time)+ "millseconds");
   }
}

######### star here:How many primes in 2 to 50000?

# start timer

$start = time();

$max_number=50000;

$start_number=2;

$total=0;

for ($ii=$start_number;$ii<=$max_number;$ii++){

if (&is_prime($ii)==1)

{$total+=1}

}

# end timer

$end = time();

# report

print "There are ",$total," primes between ",$start_number," and ",$max_number,"\n";

print "Time taken was ", ($end - $start), " seconds";

sub is_prime() {

my ($number) = $_[0];

my ($si)=2;

for ($si;$si<$number;$si++){

if ($number % $si == 0) {

return 0;}

}

return 1

}

---------------------------------
Discover Yahoo!
Find restaurants, movies, travel & more fun for the weekend. Check it out!

--
David Mitchell
Software Engineer
Telogis

Michael Tan wrote:

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?

Your programs aren't the same. The Java and Perl program don't use objects, the Ruby version does. Both the Perl and the Java version could overflow, if numbers get too big, the Ruby program doesn't suffer from this.

And look, I just made the Ruby version, faster, smaller and more object oriented:

class Integer
  def prime?
    not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
  end
end
######### star here:How many primes in 2 to 50000?
start_number, max_number = 2, 50000
time = Time.now.to_f
total = (start_number..max_number).inject(0) { |s,i| s + (i.prime? ? 1 : 0) }
time = Time.now.to_f - time
puts "There are #{total} primes between #{start_number} and #{max_number}"
puts "Time taken %.3f seconds" % time

Now do the same in the other two languages...

···

--
Florian Frank

if you just want a fast ruby version:

   harp:~ > cat prime_inline.rb
   def benchmark label, code
     STDOUT.sync = true
     puts "#{ '=' * 16 }\n#{ label }\n#{ '=' * 16 }"
     fork do
       GC.disable
       a = Time::now.to_f
       code.call
       b = Time::now.to_f
       puts " @ #{ b - a }"
     end
     Process::wait
   end

   prime_test = lambda{ (2 ... (2 ** 14)).each{|n| n.prime?} }

   class Fixnum
     def prime?
      (2...self).each{|i| return false if self % i == 0}
        return true
     end
   end
   benchmark 'pure ruby', prime_test

   require 'inline'
   class Fixnum
     inline do |builder|
       builder.c_raw <<-src
         static VALUE
         is_prime_c (int argc, VALUE *argv, VALUE self) {
           long i, n = FIX2LONG (self);
           for (i = 2; i < n; i++) if (n % i == 0) return Qfalse;
           return Qtrue;
         }
       src
     end
     alias prime? is_prime_c
   end
   benchmark 'inline c', prime_test

   harp:~ > ruby prime_inline.rb

···

On Wed, 22 Jun 2005, Michael Tan wrote:

--0-1157793495-1119383752=:96009
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

   ================
   pure ruby
   ================
    @ 14.9205560684204
   ================
   inline c
   ================
    @ 0.539831876754761

so that's about two orders of magnitude speed-up for less than 10 extra lines
of code - and you still get nice things like overflow safety.

hth.

-a
--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
My religion is very simple. My religion is kindness.
--Tenzin Gyatso

===============================================================================

Michael Tan wrote:

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13...

Refer to the simple programs on The Great Computer Language Shootout -
then you can blame those guys for doing meaningless benchmarking rather
than taking the heat yourself :slight_smile:

http://shootout.alioth.debian.org/great/benchmark.php?test=all&lang=ruby&lang2=java&sort=fullcpu

Michael Tan wrote:

1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

Ruby about half the speed of Perl is about right, judging from my own comparisons.

Personally, I consider it a good tradeoff to have code half the speed, if it means I never have to write in Perl again.

mathew

With some very minor modifications to the original code (I did upto instead of for and wrapped is_prime in a class), none of which were algorithmic improvements (ugh):

Modified is_prime code:

class Primer
   def is_prime(number)
     2.upto(number-1) do |i|
       return false if number % i == 0
     end
     return true
   end
end

NORMAL:

% rm -rf ~/.ruby_inline/; ruby primes.rb 50000
There are 5133 primes between 2 and 50000
Time taken 237.315160036087 seconds

     (whoa. my laptop is a slowpoke! oh yeah, I'm on battery!)

ONE EXTRA CMD-LINE TOKEN:

% rm -rf ~/.ruby_inline/; ruby -rzenoptimize primes.rb 50000
*** Optimizer threshold tripped!! Optimizing Primer.is_prime
There are 5133 primes between 2 and 50000
Time taken 2.81669783592224 seconds

That said... what did we learn from this thread?

     Yes... benchmarks are dumb (see also, 3 lines down)
         That there is no accounting for taste (ugliest code/algorithm ever).
             A good algorithm goes a long way.
                 2/3rds of the ppl are going to mis-analyze anyhow.

... Nothing really.

···

On Jun 21, 2005, at 12:55 PM, Michael Tan wrote:

Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

--
ryand-ruby@zenspider.com - Seattle.rb - Seattle.rb | Home
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

Hi!

1. Ruby result: 101 seconds
2. Java result:9.8 seconds
3. Perl result:62 seconds

My Ruby implementation of a sieve fishing for primes takes 4.8 seconds
or so on an AMD K6 running at 350 MHz (128 MB, Aurox Linux) while the
original program takes about 1362 seconds. Rule of thumb: Improving
algorithm good, improving hardware or language bad (to use the famous
animal farm style :slight_smile:

time=Time.now.to_f
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_f - time

What does this program do? First it assumes that 2 is the only even
prime so after initializing the list of primes to 2 it can restrict
the search to odd numbers. Iterating over the candidates for primes it
first computes the square root (to improve efficiency of comparisms
the value is converted into an integer). Iterating over all primes
already collected the program tries to find a prime factor of the
candidate for prime - i.e. a number where the remainder after division
by the prime in question is zero. If such a factor is found the loop
searching for a prime factor is aborted. The same happens if the
factor in question exceeds the pre-computed square root. Just after
the checking loop the program looks if the most recently checked
potential prime factor is no prime factor - i.e. division of the
candidate for prime by the potential factor yields nonzero remainder.
If that is the case a new prime has been found and the candidate for
prime is added to the list of primes.

Josef 'Jupp' SCHUGT

···

At Wed, 22 Jun 2005 04:55:58 +0900, Michael Tan wrote:
--
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.

Florian Frank wrote:
[...]

For correctness, perhaps even:

class Integer
def prime?

       return false if self < 2

···

   not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
end
end

--
Florian Frank

* Florian Frank <flori@nixe.ping.de> [2005-06-22 05:40:14 +0900]:

def prime?
   not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
end
end

Have you tried skipping even numbers (excluding 2 of course)?
That should give you a little more speed.

···

--
Jim Freeze

Ara.T.Howard@noaa.gov said:

   harp:~ > ruby prime_inline.rb
   ================
   pure ruby
   ================
    @ 14.9205560684204
   ================
   inline c
   ================
    @ 0.539831876754761

I was thinking a RubyInline example would be nice, thanks for providing it
Ara. Yet again this shows that Ruby (and the solid community behind it)
rocks!

Ryan

How about using a better algorithm than Eratosthenes sieve invented
thousands of years ago. In late 2003 a new method was published that
computes the first n primes using binary quadratic forms. This will
give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).

For theoretical description see:

And for a sample implementation in C
http://cr.yp.to/primegen.html

cheers,
zsombor

···

--
http://deezsombor.blogspot.com

Florian Frank wrote:

And look, I just made the Ruby version, faster, smaller and more object
oriented:
...
Now do the same in the other two languages...

Okay, here's the Perl version:

#!/usr/bin/perl -w
use Math::Big 'primes';
my $max = 50000;
my $start = time();
my $total = primes($max);
my $time = time() - $start;
print "There are $total primes below $max.\n";
print "Time taken was $time\n";

On my system I get 27 vs. 192 for the original Perl version (which is
not written very perlishly). Sure, this is cheating. CPAN is like
institutionalized cheating, and I love it. :slight_smile: In fact, one of the
reasons I started lurking in the Ruby group is that I think Ruby (with
Gems) is closer to developing a CPAN-like system than Python, and thus
I have decided to learn Ruby instead of Python.

- Mark.

of course... I spaced out and didn't fix my subject line.

···

--
ryand-ruby@zenspider.com - Seattle.rb - http://www.zenspider.com/seattle.rb
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

Ryan Davis wrote:
-snip-

That said... what did we learn from this thread?

     Yes... benchmarks are dumb (see also, 3 lines down)
         That there is no accounting for taste (ugliest code/
algorithm ever).
             A good algorithm goes a long way.
                 2/3rds of the ppl are going to mis-analyze anyhow.

.. Nothing really.

What we learn depends on many things, including
- initial expectations, are we even in the right ball-park?
- openmindedness, are we willing to hear other peoples interpretations?
- ...

So if we initially expected a little Ruby program to have the same
performance characteristics as a roughly equivalent Java program, we
learned quite a lot.

(We don't all know the same things.)

Hi!

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

···

At Fri, 24 Jun 2005 00:02:42 +0200, Josef 'Jupp' SCHUGT wrote:
--
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.

Jim Freeze wrote:

Have you tried skipping even numbers (excluding 2 of course)?

Not me, but some guy did 2500 years ago.

That should give you a little more speed.

It depends on how far you take your idea. It could get really slow on a real computer, if you do it with big numbers.

···

--
Florian Frank

Jim Freeze said:

Have you tried skipping even numbers (excluding 2 of course)?
That should give you a little more speed.

In my informal tests, Florian's version is already about 70 times faster
than the original one. It is also about 3.5 times faster than the naive
Java version.

Good job Florian!

Also, if the algorithm cannot be optimized in this way, the slow parts can
be coded in C (which is pretty easy with RubyInline.)

When you consider that coding in Java in like having your hands tied
compared to Ruby, I'd take the "slow" Ruby anyday (and I've been
programming Java since 1997...Ruby since 2001.) Just the fact that you
need a monster like Eclipse to productively program Java makes me a bit
hesitant to continue using it. But I don't want to start language
wars...Java has its uses, like any language.

Ryan

ruby inline is simply amazing - three cheers for ryan (the other one :wink: )

ciao.

-a

···

On Wed, 22 Jun 2005, Ryan Leavengood wrote:

Ara.T.Howard@noaa.gov said:

   harp:~ > ruby prime_inline.rb
   ================
   pure ruby
   ================
    @ 14.9205560684204
   ================
   inline c
   ================
    @ 0.539831876754761

I was thinking a RubyInline example would be nice, thanks for providing it
Ara. Yet again this shows that Ruby (and the solid community behind it)
rocks!

--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
My religion is very simple. My religion is kindness.
--Tenzin Gyatso

===============================================================================