summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-09-04 16:10:06 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-09-04 16:10:06 +0000
commit8f8bf8243d810d49a98dcb2713b14de3bf3716e0 (patch)
treec6abe5461a6b3c784d613a9284ca9a583170d8fd
parentff5a4c998340eff7c3d6867836d387d7a5159dec (diff)
* 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
-rw-r--r--ChangeLog10
-rw-r--r--bignum.c32
-rw-r--r--ext/-test-/bignum/depend1
-rw-r--r--ext/-test-/bignum/div.c25
-rw-r--r--internal.h1
-rw-r--r--test/-ext-/bignum/test_div.rb19
6 files changed, 88 insertions, 0 deletions
diff --git a/ChangeLog b/ChangeLog
index 5bcb5345899..ecd1137cff1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -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.
diff --git a/bignum.c b/bignum.c
index ec1411e7f4d..6092376061e 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 4634ecf627c..c65482236af 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 00000000000..1706df99b55
--- /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 aef6193fb33..f458582a33d 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 00000000000..ec12e88c912
--- /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