From 42a3e0dc55620664af3e6253f324711316b93934 Mon Sep 17 00:00:00 2001 From: akr Date: Fri, 6 Sep 2013 12:07:08 +0000 Subject: * 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. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42858 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 16 ++++++++++++ ext/-test-/rational/depend | 3 +++ ext/-test-/rational/extconf.rb | 7 ++++++ ext/-test-/rational/rat.c | 36 +++++++++++++++++++++++++++ internal.h | 6 +++++ rational.c | 55 ++++++++++++++++++++++++++++++++++++++++- test/-ext-/rational/test_rat.rb | 31 +++++++++++++++++++++++ 7 files changed, 153 insertions(+), 1 deletion(-) create mode 100644 ext/-test-/rational/depend create mode 100644 ext/-test-/rational/extconf.rb create mode 100644 ext/-test-/rational/rat.c create mode 100644 test/-ext-/rational/test_rat.rb diff --git a/ChangeLog b/ChangeLog index c115fd511b..99f4cca4d9 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +Fri Sep 6 21:04:10 2013 Tanaka Akira + + * 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 * 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 +#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) +#define USE_GMP +#include +#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 -- cgit v1.2.3