This is a multi-part message in MIME format. --------------030806030908090809070504 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 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ÛÕail&aid034&group_idB6&atid98 Thanks, Kurt Stephens http://kurtstephens.com --------------030806030908090809070504 Content-Type: text/x-diff; name uby-1.8.6-fixnum-gcd-patch.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename uby-1.8.6-fixnum-gcd-patch.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 ! ) { + rb_raise(rb_eArgError, "wrong number of arguments (%d for %d)", argc, 1); + } + if ( FIXNUM_P(argv[0]) ) { + long a IX2LONG(self); + long b IX2LONG(argv[0]); + long min < 0 ? - a : a; + long max < 0 ? - b : b; + while ( min > 0 ) { + long tmp in; + min ax % min; + max mp; + } + 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 --------------030806030908090809070504 Content-Type: text/x-diff; name uby-1.9-fixnum-gcd-patch.diff" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename uby-1.9-fixnum-gcd-patch.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 ! ) { + 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 IX2LONG(self); + long b IX2LONG(argv[0]); + long min < 0 ? - a : a; + long max < 0 ? - b : b; + while ( min > 0 ) { + long tmp in; + min ax % min; + max mp; + } + 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 --------------030806030908090809070504 Content-Type: application/x-ruby; name uby-fixnum-gcd-test.rb" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename uby-fixnum-gcd-test.rb" IwojIFJ1bjoKIwojICAuL21pbmlydWJ5IC1JIGxpYiBydWJ5LWZpeG51bS1nY2QtdGVzdC5y YgojCnJlcXVpcmUgJ2JlbmNobWFyaycKcmVxdWlyZSAncmF0aW9uYWwnICMgSW50ZWdlciNn Y2QKCnVzZV9kaWdlc3RfbWQ1ID0gQVJHVi5pbmNsdWRlPygnLS1kaWdlc3QnKSAmJgpiZWdp bgpyZXF1aXJlICdkaWdlc3QvbWQ1Jwp0cnVlCnJlc2N1ZSBFeGNlcHRpb24gPT4gZXJyCmZh bHNlCmVuZAoKc3JhbmQoMTIxMjM5OCkKCmFyZ3MgPSAoMC4uLjEwMDAwKS5tYXAgZG8gfCB4 IHwKICBbIHJhbmQoMTAwMDAwKS50b19pLCByYW5kKDEwMDAwMCkudG9faSBdCmVuZAojIHB1 dHMgYXJncy5pbnNwZWN0CgpkID0gdXNlX2RpZ2VzdF9tZDUgJiYgRGlnZXN0OjpNRDUubmV3 IAoKQmVuY2htYXJrLmJtYm0gZG8gfCBibSB8CiAgYm0ucmVwb3J0KCJGaXhudW0jZ2NkIikg ZG8KICAgIDEwMC50aW1lcyBkbyAKICAgICAgYXJncy5lYWNoIGRvIHwgeCwgeSB8CiAgICAg ICAgciA9IHguZ2NkKHkpCiAgICAgICAgZCA8PCByLnRvX3MgaWYgZAogICAgICBlbmQKICAg IGVuZAogIGVuZAplbmQKCnB1dHMgZC5oZXhkaWdlc3QgaWYgZAoK --------------030806030908090809070504--