From: Mathieu Bouchard <matju@...>
Date: 2006-02-17T10:34:26+09:00
Subject: Re: patch for rational.rb (gcd)

On Fri, 17 Feb 2006, Daniel Berger wrote:

> Anyway, here's the proposed patch (which I'm proposing for gcd rather than
> gcd2, since DateTime.parse would benefit from this).

The version of gcd that uses >>=, which is often called "binary gcd", may
be faster than euclid's gcd. The % operator is slow, and if it doesn't 
look like it, it's because Ruby is slow.

If Ruby were routinely compiled to C I'd recommend the binary gcd.

In the light of your benchmark I recommend whichever is faster, especially 
if it is faster using YARV. Have you tried with YARV?

BTW, here, i have ruby 1.9, on a K8 @ 2010 MHz in 32-bit mode. gcd2
and gcd3 have equal speed (with MAX=10000):

gcd   4.090000   0.000000   4.090000 (  4.141507)
gcd2  1.740000   0.000000   1.740000 (  1.766060)
gcd3  1.740000   0.000000   1.740000 (  1.764918)

gcd2 looked like it would be slow (with the divmod and lack of
substraction). I don't understand why it's any fast. Does it have anything 
to do with the GC ? gcd2 creates a lot of Arrays.

Test with yarv on the same machine:

gcd   1.960000   0.000000   1.960000 (  1.980669)
gcd2  0.570000   0.000000   0.570000 (  0.584279)
gcd3  0.580000   0.000000   0.580000 (  0.591337)

i vote for your code.

 _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - t�l:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montr�al QC Canada