From 8f8bf8243d810d49a98dcb2713b14de3bf3716e0 Mon Sep 17 00:00:00 2001 From: akr Date: Wed, 4 Sep 2013 16:10:06 +0000 Subject: * bignum.c (rb_big_divrem_normal): New function. * internal.h (rb_big_divrem_normal): Declared. * ext/-test-/bignum/div.c: New file. * test/-ext-/bignum/test_div.rb: New file. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42834 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 10 ++++++++++ bignum.c | 32 ++++++++++++++++++++++++++++++++ ext/-test-/bignum/depend | 1 + ext/-test-/bignum/div.c | 25 +++++++++++++++++++++++++ internal.h | 1 + test/-ext-/bignum/test_div.rb | 19 +++++++++++++++++++ 6 files changed, 88 insertions(+) create mode 100644 ext/-test-/bignum/div.c create mode 100644 test/-ext-/bignum/test_div.rb diff --git a/ChangeLog b/ChangeLog index 5bcb534589..ecd1137cff 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +Thu Sep 5 00:38:32 2013 Tanaka Akira + + * bignum.c (rb_big_divrem_normal): New function. + + * internal.h (rb_big_divrem_normal): Declared. + + * ext/-test-/bignum/div.c: New file. + + * test/-ext-/bignum/test_div.rb: New file. + Thu Sep 5 00:08:44 2013 Tanaka Akira * bignum.c (bigdivrem_normal): Removed. diff --git a/bignum.c b/bignum.c index ec1411e7f4..6092376061 100644 --- a/bignum.c +++ b/bignum.c @@ -2644,6 +2644,7 @@ bary_divmod_normal(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT VALUE tmpz = 0; VALUE tmpyy = 0; + assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); assert(qds ? (xn - yn + 1) <= qn : 1); assert(rds ? yn <= rn : 1); @@ -2696,6 +2697,37 @@ bary_divmod_normal(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT ALLOCV_END(tmpz); } +VALUE +rb_big_divrem_normal(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 + BIGDIVREM_EXTRA_WORDS; + 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_normal(qds, qn, rds, rn, xds, xn, yds, yn); + + bigtrunc(q); + bigtrunc(r); + + return rb_assoc_new(q, r); +} + 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) { diff --git a/ext/-test-/bignum/depend b/ext/-test-/bignum/depend index 4634ecf627..c65482236a 100644 --- a/ext/-test-/bignum/depend +++ b/ext/-test-/bignum/depend @@ -2,5 +2,6 @@ $(OBJS): $(HDRS) $(ruby_headers) intpack.o: intpack.c $(top_srcdir)/internal.h mul.o: mul.c $(top_srcdir)/internal.h +div.o: div.c $(top_srcdir)/internal.h big2str.o: big2str.c $(top_srcdir)/internal.h str2big.o: big2str.c $(top_srcdir)/internal.h diff --git a/ext/-test-/bignum/div.c b/ext/-test-/bignum/div.c new file mode 100644 index 0000000000..1706df99b5 --- /dev/null +++ b/ext/-test-/bignum/div.c @@ -0,0 +1,25 @@ +#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 +divrem_normal(VALUE x, VALUE y) +{ + return rb_big_norm(rb_big_divrem_normal(big(x), big(y))); +} + +void +Init_div(VALUE klass) +{ + rb_define_method(rb_cInteger, "big_divrem_normal", divrem_normal, 1); +} diff --git a/internal.h b/internal.h index aef6193fb3..f458582a33 100644 --- a/internal.h +++ b/internal.h @@ -696,6 +696,7 @@ VALUE rb_big_mul_balance(VALUE x, VALUE y); VALUE rb_big_mul_karatsuba(VALUE x, VALUE y); VALUE rb_big_mul_toom3(VALUE x, VALUE y); VALUE rb_big_sq_fast(VALUE x); +VALUE rb_big_divrem_normal(VALUE x, VALUE y); VALUE rb_big2str_poweroftwo(VALUE x, int base); VALUE rb_big2str_generic(VALUE x, int base); VALUE rb_str2big_poweroftwo(VALUE arg, int base, int badcheck); diff --git a/test/-ext-/bignum/test_div.rb b/test/-ext-/bignum/test_div.rb new file mode 100644 index 0000000000..ec12e88c91 --- /dev/null +++ b/test/-ext-/bignum/test_div.rb @@ -0,0 +1,19 @@ +require 'test/unit' +require "-test-/bignum" + +class TestBignum < Test::Unit::TestCase + class TestDiv < Test::Unit::TestCase + + SIZEOF_BDIGITS = Bignum::SIZEOF_BDIGITS + BITSPERDIG = Bignum::BITSPERDIG + BDIGMAX = (1 << BITSPERDIG) - 1 + + def test_divrem_normal + x = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 3 + y = (1 << BITSPERDIG) | 1 + q = (1 << BITSPERDIG) | 1 + r = 2 + assert_equal([q, r], x.big_divrem_normal(y)) + end + end +end -- cgit v1.2.3