ruby-changes:30761
From: akr <ko1@a...>
Date: Thu, 5 Sep 2013 08:22:34 +0900 (JST)
Subject: [ruby-changes:30761] akr:r42840 (trunk): * bignum.c (GMP_DIV_DIGITS): New macro.
akr 2013-09-05 08:22:27 +0900 (Thu, 05 Sep 2013) New Revision: 42840 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42840 Log: * bignum.c (GMP_DIV_DIGITS): New macro. (bary_divmod_gmp): New function. (rb_big_divrem_gmp): Ditto. (bary_divmod_branch): Ditto. (bary_divmod): Use bary_divmod_branch. (bigdivrem): Ditto. * internal.h (rb_big_divrem_gmp): Declared. Modified files: trunk/ChangeLog trunk/bignum.c trunk/ext/-test-/bignum/div.c trunk/internal.h trunk/test/-ext-/bignum/test_div.rb trunk/test/ruby/test_bignum.rb Index: ChangeLog =================================================================== --- ChangeLog (revision 42839) +++ ChangeLog (revision 42840) @@ -1,3 +1,14 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Thu Sep 5 08:20:58 2013 Tanaka Akira <akr@f...> + + * bignum.c (GMP_DIV_DIGITS): New macro. + (bary_divmod_gmp): New function. + (rb_big_divrem_gmp): Ditto. + (bary_divmod_branch): Ditto. + (bary_divmod): Use bary_divmod_branch. + (bigdivrem): Ditto. + + * internal.h (rb_big_divrem_gmp): Declared. + Thu Sep 5 06:22:42 2013 Tanaka Akira <akr@f...> * bignum.c (bary_divmod_normal): Reduce temporary array allocations. Index: ext/-test-/bignum/div.c =================================================================== --- ext/-test-/bignum/div.c (revision 42839) +++ ext/-test-/bignum/div.c (revision 42840) @@ -18,8 +18,19 @@ divrem_normal(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/div.c#L18 return rb_big_norm(rb_big_divrem_normal(big(x), big(y))); } +#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) +static VALUE +divrem_gmp(VALUE x, VALUE y) +{ + return rb_big_norm(rb_big_divrem_gmp(big(x), big(y))); +} +#else +#define divrem_gmp rb_f_notimplement +#endif + void Init_div(VALUE klass) { rb_define_method(rb_cInteger, "big_divrem_normal", divrem_normal, 1); + rb_define_method(rb_cInteger, "big_divrem_gmp", divrem_gmp, 1); } Index: internal.h =================================================================== --- internal.h (revision 42839) +++ internal.h (revision 42840) @@ -704,6 +704,7 @@ VALUE rb_str2big_normal(VALUE arg, int b https://github.com/ruby/ruby/blob/trunk/internal.h#L704 VALUE rb_str2big_karatsuba(VALUE arg, int base, int badcheck); #if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) VALUE rb_big_mul_gmp(VALUE x, VALUE y); +VALUE rb_big_divrem_gmp(VALUE x, VALUE y); VALUE rb_big2str_gmp(VALUE x, int base); VALUE rb_str2big_gmp(VALUE arg, int base, int badcheck); #endif Index: bignum.c =================================================================== --- bignum.c (revision 42839) +++ bignum.c (revision 42840) @@ -135,6 +135,7 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdi https://github.com/ruby/ruby/blob/trunk/bignum.c#L135 #define KARATSUBA_MUL_DIGITS 70 #define TOOM3_MUL_DIGITS 150 +#define GMP_DIV_DIGITS 20 #define GMP_BIG2STR_DIGITS 20 #define GMP_STR2BIG_DIGITS 20 @@ -2278,7 +2279,7 @@ bary_mul_gmp(BDIGIT *zds, size_t zn, con https://github.com/ruby/ruby/blob/trunk/bignum.c#L2279 mpz_import(y, yn, -1, sizeof(BDIGIT), 0, nails, yds); mpz_mul(z, x, y); } - mpz_export (zds, &count, -1, sizeof(BDIGIT), 0, nails, z); + mpz_export(zds, &count, -1, sizeof(BDIGIT), 0, nails, z); BDIGITS_ZERO(zds+count, zn-count); mpz_clear(x); mpz_clear(y); @@ -2730,6 +2731,100 @@ rb_big_divrem_normal(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L2731 return rb_assoc_new(q, r); } +#ifdef USE_GMP +static void +bary_divmod_gmp(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) +{ + const size_t nails = (sizeof(BDIGIT)-SIZEOF_BDIGITS)*CHAR_BIT; + mpz_t x, y, q, r; + size_t count; + + assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); + assert(qds ? (xn - yn + 1) <= qn : 1); + assert(rds ? yn <= rn : 1); + assert(qds || rds); + + mpz_init(x); + mpz_init(y); + if (qds) mpz_init(q); + if (rds) mpz_init(r); + + mpz_import(x, xn, -1, sizeof(BDIGIT), 0, nails, xds); + mpz_import(y, yn, -1, sizeof(BDIGIT), 0, nails, yds); + + if (!rds) { + mpz_fdiv_q(q, x, y); + } + else if (!qds) { + mpz_fdiv_r(r, x, y); + } + else { + mpz_fdiv_qr(q, r, x, y); + } + + mpz_clear(x); + mpz_clear(y); + + if (qds) { + mpz_export(qds, &count, -1, sizeof(BDIGIT), 0, nails, q); + BDIGITS_ZERO(qds+count, qn-count); + mpz_clear(q); + } + + if (rds) { + mpz_export(rds, &count, -1, sizeof(BDIGIT), 0, nails, r); + BDIGITS_ZERO(rds+count, rn-count); + mpz_clear(r); + } +} + +VALUE +rb_big_divrem_gmp(VALUE x, VALUE y) +{ + size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), qn, rn; + BDIGIT *xds = BDIGITS(x), *yds = BDIGITS(y), *qds, *rds; + VALUE q, r; + + BARY_TRUNC(yds, yn); + if (yn == 0) + rb_num_zerodiv(); + BARY_TRUNC(xds, xn); + + if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) + return rb_assoc_new(LONG2FIX(0), x); + + qn = xn - yn + 1; + q = bignew(qn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y)); + qds = BDIGITS(q); + + rn = yn; + r = bignew(rn, RBIGNUM_SIGN(x)); + rds = BDIGITS(r); + + bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn); + + bigtrunc(q); + bigtrunc(r); + + RB_GC_GUARD(x); + RB_GC_GUARD(y); + + return rb_assoc_new(q, r); +} +#endif + +static void +bary_divmod_branch(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) +{ +#ifdef USE_GMP + if (GMP_DIV_DIGITS < xn) { + bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn); + return; + } +#endif + bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn); +} + static void bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { @@ -2771,7 +2866,7 @@ bary_divmod(BDIGIT *qds, size_t qn, BDIG https://github.com/ruby/ruby/blob/trunk/bignum.c#L2866 BDIGITS_ZERO(rds+2, rn-2); } else { - bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn); + bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn); } } @@ -6006,7 +6101,7 @@ bigdivrem(VALUE x, VALUE y, volatile VAL https://github.com/ruby/ruby/blob/trunk/bignum.c#L6101 rds = NULL; } - bary_divmod_normal(qds, qn, rds, rn, xds, xn, yds, yn); + bary_divmod_branch(qds, qn, rds, rn, xds, xn, yds, yn); if (divp) { bigtrunc(q); Index: test/ruby/test_bignum.rb =================================================================== --- test/ruby/test_bignum.rb (revision 42839) +++ test/ruby/test_bignum.rb (revision 42840) @@ -598,6 +598,9 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_bignum.rb#L598 end def test_interrupt_during_bigdivrem + if defined?(Bignum::GMP_VERSION) + return # GMP doesn't support interrupt during an operation. + end return unless Process.respond_to?(:kill) begin trace = [] Index: test/-ext-/bignum/test_div.rb =================================================================== --- test/-ext-/bignum/test_div.rb (revision 42839) +++ test/-ext-/bignum/test_div.rb (revision 42840) @@ -15,5 +15,14 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/-ext-/bignum/test_div.rb#L15 r = 2 assert_equal([q, r], x.big_divrem_normal(y)) end + + def test_divrem_gmp + x = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 3 + y = (1 << BITSPERDIG) | 1 + q = (1 << BITSPERDIG) | 1 + r = 2 + assert_equal([q, r], x.big_divrem_gmp(y)) + rescue NotImplementedError + end end end -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/