diff options
| -rw-r--r-- | ChangeLog | 10 | ||||
| -rw-r--r-- | bignum.c | 32 | ||||
| -rw-r--r-- | ext/-test-/bignum/depend | 1 | ||||
| -rw-r--r-- | ext/-test-/bignum/div.c | 25 | ||||
| -rw-r--r-- | internal.h | 1 | ||||
| -rw-r--r-- | test/-ext-/bignum/test_div.rb | 19 |
6 files changed, 88 insertions, 0 deletions
@@ -1,3 +1,13 @@ +Thu Sep 5 00:38:32 2013 Tanaka Akira <akr@fsij.org> + + * 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 <akr@fsij.org> * bignum.c (bigdivrem_normal): Removed. @@ -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 |