summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog11
-rw-r--r--bignum.c101
-rw-r--r--ext/-test-/bignum/div.c11
-rw-r--r--internal.h1
-rw-r--r--test/-ext-/bignum/test_div.rb9
-rw-r--r--test/ruby/test_bignum.rb3
6 files changed, 133 insertions, 3 deletions
diff --git a/ChangeLog b/ChangeLog
index 51fb6a9ae0..8714b62aca 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+Thu Sep 5 08:20:58 2013 Tanaka Akira <akr@fsij.org>
+
+ * 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@fsij.org>
* bignum.c (bary_divmod_normal): Reduce temporary array allocations.
diff --git a/bignum.c b/bignum.c
index 308af6b2f3..b7a09ae146 100644
--- a/bignum.c
+++ b/bignum.c
@@ -135,6 +135,7 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGITS % SIZEOF_LONG == 0);
#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, const BDIGIT *xds, size_t xn, const BDIGIT
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)
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, BDIGIT *rds, size_t rn, const BDIGIT *xds, s
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 VALUE *divp, volatile VALUE *modp)
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);
diff --git a/ext/-test-/bignum/div.c b/ext/-test-/bignum/div.c
index 1706df99b5..2853ebef1c 100644
--- a/ext/-test-/bignum/div.c
+++ b/ext/-test-/bignum/div.c
@@ -18,8 +18,19 @@ divrem_normal(VALUE x, VALUE y)
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);
}
diff --git a/internal.h b/internal.h
index f458582a33..e2c90e79b6 100644
--- a/internal.h
+++ b/internal.h
@@ -704,6 +704,7 @@ VALUE rb_str2big_normal(VALUE arg, int base, int badcheck);
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
diff --git a/test/-ext-/bignum/test_div.rb b/test/-ext-/bignum/test_div.rb
index ec12e88c91..882d2d164f 100644
--- a/test/-ext-/bignum/test_div.rb
+++ b/test/-ext-/bignum/test_div.rb
@@ -15,5 +15,14 @@ class TestBignum < Test::Unit::TestCase
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
diff --git a/test/ruby/test_bignum.rb b/test/ruby/test_bignum.rb
index 5a91a2a6b6..4d87d5fca3 100644
--- a/test/ruby/test_bignum.rb
+++ b/test/ruby/test_bignum.rb
@@ -598,6 +598,9 @@ class TestBignum < Test::Unit::TestCase
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 = []
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 18:26:13 +0000