diff options
| -rw-r--r-- | ChangeLog | 16 | ||||
| -rw-r--r-- | ext/-test-/rational/depend | 3 | ||||
| -rw-r--r-- | ext/-test-/rational/extconf.rb | 7 | ||||
| -rw-r--r-- | ext/-test-/rational/rat.c | 36 | ||||
| -rw-r--r-- | internal.h | 6 | ||||
| -rw-r--r-- | rational.c | 55 | ||||
| -rw-r--r-- | test/-ext-/rational/test_rat.rb | 31 |
7 files changed, 153 insertions, 1 deletions
@@ -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 0000000000..a43589042b --- /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 0000000000..bd658def46 --- /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 0000000000..49e216aa41 --- /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 e10bf64b46..795749dd5b 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 ee0e1689e9..d70dfd41ab 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 0000000000..ef7e7fe535 --- /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 |