[前][次][番号順一覧][スレッド一覧]

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/

[前][次][番号順一覧][スレッド一覧]