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

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

Jim Freeze
Guest
Posts: n/a

 06-22-2005
* Ken Kunz <(E-Mail Removed)> [2005-06-22 07:20:36 +0900]:

> user system total real
> original: 171.767000 0.020000 171.787000 (174.627000)
> Florian's: 2.804000 0.010000 2.814000 ( 2.814000)
> Ken's: 1.041000 0.000000 1.041000 ( 1.042000)

That's better than I expected. I'm not sure why Florian thought
it would be slower.

--
Jim Freeze

Florian Frank
Guest
Posts: n/a

 06-22-2005
Jim Freeze wrote:

>That's better than I expected. I'm not sure why Florian thought
>it would be slower.
>
>

If you compute a sieve to find out, if a very high number is prime...

--
Florian Frank

Dee Zsombor
Guest
Posts: n/a

 06-22-2005
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:
http://www.ams.org/mcom/2004-73-246/...03-01501-1.pdf

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

cheers,
zsombor
--
http://deezsombor.blogspot.com

Roland Schmitt
Guest
Posts: n/a

 06-22-2005
irb(main):001:0> require "openssl"
=> true
irb(main):002:0> include OpenSSL
=> Object
irb(main):003:0> a=BN.new("103")
=> 103
irb(main):004:0> a.prime?(10)
=> true
irb(main):005:0> a.prime?(nil)
=> true
irb(main):006:0>

It implements the Miller-Rabin-Test.

See http://www.hmug.org/man/3/BN_is_prime.php

Dee Zsombor schrieb:
> 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:
> http://www.ams.org/mcom/2004-73-246/...03-01501-1.pdf
>
> And for a sample implementation in C
> http://cr.yp.to/primegen.html
>
> cheers,
> zsombor
> --
> http://deezsombor.blogspot.com
>
>
>

Mark Thomas
Guest
Posts: n/a

 06-22-2005
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. 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.

Ryan Davis
Guest
Posts: n/a

 06-23-2005

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

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?

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.

--
http://www.velocityreviews.com/forums/(E-Mail Removed) - Seattle.rb - http://www.zenspider.com/
seattle.rb
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

Ryan Davis
Guest
Posts: n/a

 06-23-2005
of course... I spaced out and didn't fix my subject line.

--
(E-Mail Removed) - Seattle.rb - http://www.zenspider.com/
seattle.rb
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

Dee Zsombor
Guest
Posts: n/a

 06-23-2005
As far as I understood from Miller-Rabin-Test is for determining if a
number is prime with a _given_ _probability_. It is a very efficient
algortithm for that.
primes less than given number. And that is an entirely different
problem, even if you woud do MR in a loop you would not get the same
results as Atkin sieve.

Dee Zsombor
Guest
Posts: n/a

 06-23-2005
As far as I understood from Miller-Rabin-Test is for determining if a
number is prime with a _given_ _probability_. It is a very efficient
algortithm for that.
primes less than given number. And that is an entirely different
problem, even if you woud do MR in a loop you would not get the same
results as Atkin sieve.

--
http://deezsombor.blogspot.com

Brian Candler
Guest
Posts: n/a

 06-23-2005
On Wed, Jun 22, 2005 at 10:50:36PM +0900, Mark Thomas wrote:
> 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. 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.

It's perhaps worth mentioning that although Ruby is about 1/3rd of the size
of Perl, it has a far more complete standard library.

A base Ruby install includes, amongst other things: SSL, base64 encoding/
decoding, MD5/SHA1 hashing, XML/YAML parsing, HTTP client and server, and
remote method calls (DRb, SOAP, XMLRPC).

I think recent version of Perl have accumulated MIME::Base64, but the others