Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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


 
Reply With Quote
 
 
 
 
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



 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
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
>
>
>




 
Reply With Quote
 
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.

 
Reply With Quote
 
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?

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.



--
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




 
Reply With Quote
 
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




 
Reply With Quote
 
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.
The Atkins sieve (binary quadratic forms) is about generating all
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.

 
Reply With Quote
 
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.
The Atkins sieve (binary quadratic forms) is about generating all
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

 
Reply With Quote
 
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
are still extensions you have to download and install.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to convert Seconds to X Hours Y Minutes Z Seconds? 00_CP_D12 ASP .Net 3 02-22-2008 10:37 AM
Can't find par loader at C:/Perl/site/lib/PAR/Packer.pm line 101. osoeder@gmx.de Perl Misc 0 06-07-2007 02:58 PM
convert seconds to hours:minutes:seconds `p Ruby 7 12-14-2005 03:32 PM
Convert seconds to minutes and seconds tshad ASP .Net 7 03-11-2005 11:27 PM
Converting seconds to (Days, Hours, Minutes, seconds) Stu C Programming 7 03-07-2005 08:44 AM



Advertisments