ruby-core

Can this be added to 1.8.7 and trunk?

* numeric.c (gcd): Added Fixnum#gcd(Fixnum) support in C.
Date uses Rational heavily, which calls Integer#gcd for every new
Rational.  The Integer#gcd method is generic to handle Bignums,
but performs terribly for Fixnum#gcd(Fixnum),
which is probably the most often case.

The 1.8.6 patch improves Fixnum#gcd performance by 1000%.
The 1.9 patch improves Fixnum#gcd performance by 300%.

See
http://rubyforge.org/tracker/?func=detail&aid=19034&group_id=426&atid=1698

Thanks,
Kurt Stephens
http://kurtstephens.com

Attachments (3)

ruby-1.8.6-fixnum-gcd-patch.diff (2.15 KB, text/x-diff)

Index: ruby-1.8.6-svn/numeric.c
===================================================================
--- ruby-1.8.6-svn/numeric.c	(revision 15827)
+++ ruby-1.8.6-svn/numeric.c	(working copy)
@@ -2380,6 +2380,41 @@
     }
 }
 
+
+/*
+ * call-seq:
+ *   Fixnum.gcd(Integer)    =>  Integer
+ *
+ * Returns the <em>greatest common denominator</em> of the two numbers (+self+
+ * and +n+).
+ *
+ * This is a specialization of <code>Integer#gcd</code> for Fixnum arguments.
+ * See <code>rational.rb</code> for more details.
+ *
+ */
+
+static VALUE 
+fix_gcd(int argc, VALUE *argv, VALUE self) {
+  if ( argc != 1 ) {
+    rb_raise(rb_eArgError, "wrong number of arguments (%d for %d)", argc, 1);
+  }
+  if ( FIXNUM_P(argv[0]) ) {
+    long a = FIX2LONG(self);
+    long b = FIX2LONG(argv[0]);
+    long min = a < 0 ? - a : a;
+    long max = b < 0 ? - b : b;
+    while ( min > 0 ) {
+      long tmp = min;
+      min = max % min;
+      max = tmp;
+    }
+    return LONG2FIX(max);
+  } else {
+    return rb_call_super(1, argv);
+  }
+}
+
+
 /*
  * call-seq:
  *   ~fix     => integer
@@ -2904,6 +2939,7 @@
     rb_define_method(rb_cFixnum, "modulo", fix_mod, 1);
     rb_define_method(rb_cFixnum, "divmod", fix_divmod, 1);
     rb_define_method(rb_cFixnum, "quo", fix_quo, 1);
+    rb_define_method(rb_cFixnum, "gcd", fix_gcd, -1);
     rb_define_method(rb_cFixnum, "**", fix_pow, 1);
 
     rb_define_method(rb_cFixnum, "abs", fix_abs, 0);
Index: ruby-1.8.6-svn/ChangeLog
===================================================================
--- ruby-1.8.6-svn/ChangeLog	(revision 15827)
+++ ruby-1.8.6-svn/ChangeLog	(working copy)
@@ -1,3 +1,12 @@
+Sun Mar 24 03:09:01 UTC 2008  Kurt Stephens  <ks.ruby@kurtstephens.com>
+
+	* numeric.c (gcd): Added Fixnum#gcd(Fixnum) support in C.
+  	  Date uses Rational heavily, which calls Integer#gcd for every new
+	  Rational.  The Integer#gcd method is generic to handle Bignums, 
+	  but performs terribly for Fixnum#gcd(Fixnum), 
+	  which is probably the most often case.  Improves gcd performance on
+	  Fixnums by 1000%.
+
 Mon Mar  3 23:34:13 2008  GOTOU Yuuzou  <gotoyuzo@notwork.org>
 
 	* lib/webrick/httpservlet/filehandler.rb: should normalize path

ruby-1.9-fixnum-gcd-patch.diff (2.71 KB, text/x-diff)

Index: ruby-trunk/ChangeLog
===================================================================
--- ruby-trunk/ChangeLog	(revision 15827)
+++ ruby-trunk/ChangeLog	(working copy)
@@ -1,3 +1,12 @@
+Sun Mar 24 03:09:01 UTC 2008  Kurt Stephens  <ks.ruby@kurtstephens.com>
+
+	* numeric.c (gcd): Added Fixnum#gcd(Fixnum) support in C.
+  	  Date uses Rational heavily, which calls Integer#gcd for every new
+	  Rational.  The Integer#gcd method is generic to handle Bignums, 
+	  but performs terribly for Fixnum#gcd(Fixnum), 
+	  which is probably the most often case.  Improves gcd performance on
+	  Fixnums by 300%.
+
 Sun Mar 23 02:51:57 2008  Tanaka Akira  <akr@fsij.org>
 
 	* process.c (rlimit_resource_value): use NUM2RLIM.
Index: ruby-trunk/numeric.c
===================================================================
--- ruby-trunk/numeric.c	(revision 15827)
+++ ruby-trunk/numeric.c	(working copy)
@@ -2377,6 +2377,41 @@
     }
 }
 
+
+/*
+ * call-seq:
+ *   Fixnum.gcd(Integer)    =>  Integer
+ *
+ * Returns the <em>greatest common denominator</em> of the two numbers (+self+
+ * and +n+).
+ *
+ * This is a specialization of <code>Integer#gcd</code> for Fixnum arguments.
+ * See <code>rational.rb</code> for more details.
+ *
+ */
+
+static VALUE 
+fix_gcd(int argc, VALUE *argv, VALUE self) {
+  if ( argc != 1 ) {
+    rb_raise(rb_eArgError, "wrong number of arguments (%d for %d)", argc, 1);
+  }
+  if ( FIXNUM_P(argv[0]) ) {
+    /* fprintf(stderr, "Using Fixnum#gcd(Fixnum)\n"); */
+    long a = FIX2LONG(self);
+    long b = FIX2LONG(argv[0]);
+    long min = a < 0 ? - a : a;
+    long max = b < 0 ? - b : b;
+    while ( min > 0 ) {
+      long tmp = min;
+      min = max % min;
+      max = tmp;
+    }
+    return LONG2FIX(max);
+  } else {
+    return rb_call_super(1, argv);
+  }
+}
+
 static VALUE
 int_pow(long x, unsigned long y)
 {
@@ -3233,6 +3268,7 @@
     rb_define_method(rb_cFixnum, "quo", fix_quo, 1);
     rb_define_method(rb_cFixnum, "rdiv", fix_quo, 1);
     rb_define_method(rb_cFixnum, "fdiv", fix_fdiv, 1);
+    rb_define_method(rb_cFixnum, "gcd", (VALUE(*)(ANYARGS)) fix_gcd, -1);
     rb_define_method(rb_cFixnum, "**", fix_pow, 1);
 
     rb_define_method(rb_cFixnum, "abs", fix_abs, 0);
Index: ruby-trunk/test/ruby/test_fixnum.rb
===================================================================
--- ruby-trunk/test/ruby/test_fixnum.rb	(revision 15827)
+++ ruby-trunk/test/ruby/test_fixnum.rb	(working copy)
@@ -245,4 +245,13 @@
     assert_equal(:foo, :foo.to_i.to_sym)
     assert_nil(0.to_sym)
   end
+
+  def test_gcd
+    assert_equal(0, 0.gcd(0))
+    assert_equal(1, 1.gcd(0))
+    assert_equal(1, 0.gcd(1))
+    assert_equal(5, 5.gcd(10))
+    assert_equal(5, 10.gcd(5))
+    assert_equal(1, 5.gcd(7))
+  end
 end

ruby-fixnum-gcd-test.rb (579 Bytes, application/x-ruby)

Thread

Prev Next

In This Thread

Prev Next