summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ChangeLog16
-rw-r--r--ext/-test-/rational/depend3
-rw-r--r--ext/-test-/rational/extconf.rb7
-rw-r--r--ext/-test-/rational/rat.c36
-rw-r--r--internal.h6
-rw-r--r--rational.c55
-rw-r--r--test/-ext-/rational/test_rat.rb31
7 files changed, 153 insertions, 1 deletions
diff --git a/ChangeLog b/ChangeLog
index c115fd5..99f4cca 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+Fri Sep 6 21:04:10 2013 Tanaka Akira <akr@fsij.org>
+
+ * rational.c: Include gmp.h if GMP is used.
+ (GMP_GCD_DIGITS): New macro.
+ (rb_gcd_gmp): New function.
+ (f_gcd_normal): Renamed from f_gcd.
+ (rb_gcd_normal): New function.
+ (f_gcd): Invoke rb_gcd_gmp or f_gcd_normal.
+
+ * internal.h (rb_gcd_normal): Declared.
+ (rb_gcd_gmp): Ditto.
+
+ * ext/-test-/rational: New directory.
+
+ * test/-ext-/rational: New directory.
+
Fri Sep 6 14:23:22 2013 Nobuyoshi Nakada <nobu@ruby-lang.org>
* win32/win32.c (clock_getres): required as well as clock_gettime().
diff --git a/ext/-test-/rational/depend b/ext/-test-/rational/depend
new file mode 100644
index 0000000..a435890
--- /dev/null
+++ b/ext/-test-/rational/depend
@@ -0,0 +1,3 @@
+$(OBJS): $(HDRS) $(ruby_headers)
+
+rat.o: rat.c $(top_srcdir)/internal.h
diff --git a/ext/-test-/rational/extconf.rb b/ext/-test-/rational/extconf.rb
new file mode 100644
index 0000000..bd658de
--- /dev/null
+++ b/ext/-test-/rational/extconf.rb
@@ -0,0 +1,7 @@
+$INCFLAGS << " -I$(topdir) -I$(top_srcdir)"
+$srcs = Dir[File.join($srcdir, "*.{#{SRC_EXT.join(%q{,})}}")]
+inits = $srcs.map {|s| File.basename(s, ".*")}
+inits.delete("init")
+inits.map! {|s|"X(#{s})"}
+$defs << "-DTEST_INIT_FUNCS(X)=\"#{inits.join(' ')}\""
+create_makefile("-test-/rational")
diff --git a/ext/-test-/rational/rat.c b/ext/-test-/rational/rat.c
new file mode 100644
index 0000000..49e216a
--- /dev/null
+++ b/ext/-test-/rational/rat.c
@@ -0,0 +1,36 @@
+#include "ruby.h"
+#include "internal.h"
+
+static VALUE
+big(VALUE x)
+{
+ if (FIXNUM_P(x))
+ return rb_int2big(FIX2LONG(x));
+ if (RB_TYPE_P(x, T_BIGNUM))
+ return x;
+ rb_raise(rb_eTypeError, "can't convert %s to Bignum",
+ rb_obj_classname(x));
+}
+
+static VALUE
+gcd_normal(VALUE x, VALUE y)
+{
+ return rb_big_norm(rb_gcd_normal(rb_to_int(x), rb_to_int(y)));
+}
+
+#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
+static VALUE
+gcd_gmp(VALUE x, VALUE y)
+{
+ return rb_big_norm(rb_gcd_gmp(big(x), big(y)));
+}
+#else
+#define gcd_gmp rb_f_notimplement
+#endif
+
+void
+Init_rational(VALUE klass)
+{
+ rb_define_method(rb_cInteger, "gcd_normal", gcd_normal, 1);
+ rb_define_method(rb_cInteger, "gcd_gmp", gcd_gmp, 1);
+}
diff --git a/internal.h b/internal.h
index e10bf64..795749d 100644
--- a/internal.h
+++ b/internal.h
@@ -733,6 +733,12 @@ int rb_execarg_run_options(const struct rb_execarg *e, struct rb_execarg *s, cha
VALUE rb_execarg_extract_options(VALUE execarg_obj, VALUE opthash);
void rb_execarg_setenv(VALUE execarg_obj, VALUE env);
+/* rational.c */
+VALUE rb_gcd_normal(VALUE self, VALUE other);
+#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
+VALUE rb_gcd_gmp(VALUE x, VALUE y);
+#endif
+
/* util.c */
extern const signed char ruby_digit36_to_number_table[];
diff --git a/rational.c b/rational.c
index ee0e168..d70dfd4 100644
--- a/rational.c
+++ b/rational.c
@@ -17,10 +17,17 @@
#define NDEBUG
#include <assert.h>
+#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
+#define USE_GMP
+#include <gmp.h>
+#endif
+
#define ZERO INT2FIX(0)
#define ONE INT2FIX(1)
#define TWO INT2FIX(2)
+#define GMP_GCD_DIGITS 1
+
VALUE rb_cRational;
static ID id_abs, id_cmp, id_convert, id_eqeq_p, id_expt, id_fdiv,
@@ -276,6 +283,32 @@ k_rational_p(VALUE x)
#define k_exact_zero_p(x) (k_exact_p(x) && f_zero_p(x))
#define k_exact_one_p(x) (k_exact_p(x) && f_one_p(x))
+#ifdef USE_GMP
+VALUE
+rb_gcd_gmp(VALUE x, VALUE y)
+{
+ const size_t nails = (sizeof(BDIGIT)-SIZEOF_BDIGITS)*CHAR_BIT;
+ mpz_t mx, my, mz;
+ size_t count;
+ VALUE z;
+ long zn;
+
+ mpz_init(mx);
+ mpz_init(my);
+ mpz_init(mz);
+ mpz_import(mx, RBIGNUM_LEN(x), -1, sizeof(BDIGIT), 0, nails, RBIGNUM_DIGITS(x));
+ mpz_import(my, RBIGNUM_LEN(y), -1, sizeof(BDIGIT), 0, nails, RBIGNUM_DIGITS(y));
+
+ mpz_gcd(mz, mx, my);
+
+ zn = (mpz_sizeinbase(mz, 16) + SIZEOF_BDIGITS*2 - 1) / (SIZEOF_BDIGITS*2);
+ z = rb_big_new(zn, 1);
+ mpz_export(RBIGNUM_DIGITS(z), &count, -1, sizeof(BDIGIT), 0, nails, mz);
+
+ return rb_big_norm(z);
+}
+#endif
+
#ifndef NDEBUG
#define f_gcd f_gcd_orig
#endif
@@ -302,7 +335,7 @@ i_gcd(long x, long y)
}
inline static VALUE
-f_gcd(VALUE x, VALUE y)
+f_gcd_normal(VALUE x, VALUE y)
{
VALUE z;
@@ -333,6 +366,26 @@ f_gcd(VALUE x, VALUE y)
/* NOTREACHED */
}
+VALUE
+rb_gcd_normal(VALUE x, VALUE y)
+{
+ return f_gcd_normal(x, y);
+}
+
+inline static VALUE
+f_gcd(VALUE x, VALUE y)
+{
+#ifdef USE_GMP
+ if (TYPE(x) == T_BIGNUM && TYPE(y) == T_BIGNUM) {
+ long xn = RBIGNUM_LEN(x);
+ long yn = RBIGNUM_LEN(y);
+ if (GMP_GCD_DIGITS <= xn && GMP_GCD_DIGITS <= yn)
+ return rb_gcd_gmp(x, y);
+ }
+#endif
+ return f_gcd_normal(x, y);
+}
+
#ifndef NDEBUG
#undef f_gcd
diff --git a/test/-ext-/rational/test_rat.rb b/test/-ext-/rational/test_rat.rb
new file mode 100644
index 0000000..ef7e7fe
--- /dev/null
+++ b/test/-ext-/rational/test_rat.rb
@@ -0,0 +1,31 @@
+require 'test/unit'
+require "-test-/rational"
+
+class TestRational < Test::Unit::TestCase
+ class TestGCD < Test::Unit::TestCase
+
+ def test_gcd_normal
+ x = 2*2*3*3*3
+ y = 2*2*2*3*3
+ gcd = 2*2*3*3
+ assert_equal(gcd, x.gcd_normal(y))
+ end
+
+ def test_gcd_gmp
+ x = 2*2*3*3*3
+ y = 2*2*2*3*3
+ gcd = 2*2*3*3
+ assert_equal(gcd, x.gcd_gmp(y))
+ rescue NotImplementedError
+ end
+
+ def test_gcd_gmp_brute_force
+ -13.upto(13) {|x|
+ -13.upto(13) {|y|
+ assert_equal(x.gcd_normal(y), x.gcd_gmp(y))
+ }
+ }
+ rescue NotImplementedError
+ end
+ end
+end