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

ruby-changes:30070

From: akr <ko1@a...>
Date: Tue, 23 Jul 2013 03:35:37 +0900 (JST)
Subject: [ruby-changes:30070] akr:r42122 (trunk): * bignum.c (KARATSUBA_BALANCED): New macro.

akr	2013-07-23 03:35:27 +0900 (Tue, 23 Jul 2013)

  New Revision: 42122

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42122

  Log:
    * bignum.c (KARATSUBA_BALANCED): New macro.
      (TOOM3_BALANCED): Ditto.
      (bary_mul_balance_with_mulfunc): Use KARATSUBA_BALANCED and
      TOOM3_BALANCED.
      (rb_big_mul_balance): Relax a condition.
      (rb_big_mul_karatsuba): Use KARATSUBA_BALANCED.
      (rb_big_mul_toom3): Use TOOM3_BALANCED.
      (bary_mul_karatsuba_branch): Use KARATSUBA_BALANCED.
      (bary_mul_toom3_branch): Use TOOM3_BALANCED.

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 42121)
+++ ChangeLog	(revision 42122)
@@ -1,3 +1,15 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Tue Jul 23 03:32:23 2013  Tanaka Akira  <akr@f...>
+
+	* bignum.c (KARATSUBA_BALANCED): New macro.
+	  (TOOM3_BALANCED): Ditto.
+	  (bary_mul_balance_with_mulfunc): Use KARATSUBA_BALANCED and
+	  TOOM3_BALANCED.
+	  (rb_big_mul_balance): Relax a condition.
+	  (rb_big_mul_karatsuba): Use KARATSUBA_BALANCED.
+	  (rb_big_mul_toom3): Use TOOM3_BALANCED.
+	  (bary_mul_karatsuba_branch): Use KARATSUBA_BALANCED.
+	  (bary_mul_toom3_branch): Use TOOM3_BALANCED.
+
 Tue Jul 23 01:34:45 2013  Tanaka Akira  <akr@f...>
 
 	* bignum.c (bigdivrem_mulsub): Extracted from bigdivrem1.
Index: bignum.c
===================================================================
--- bignum.c	(revision 42121)
+++ bignum.c	(revision 42122)
@@ -121,6 +121,9 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdi https://github.com/ruby/ruby/blob/trunk/bignum.c#L121
   } \
 } while (0)
 
+#define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn))
+#define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn))
+
 #define KARATSUBA_MUL_DIGITS 70
 #define TOOM3_MUL_DIGITS 150
 
@@ -1669,7 +1672,8 @@ bary_mul_balance_with_mulfunc(BDIGIT *zd https://github.com/ruby/ruby/blob/trunk/bignum.c#L1672
     size_t r, n;
 
     assert(xl + yl <= zl);
-    assert(2 * xl <= yl || 3 * xl <= 2*(yl+2));
+    assert(xl <= yl);
+    assert(!KARATSUBA_BALANCED(xl, yl) || !TOOM3_BALANCED(xl, yl));
 
     BDIGITS_ZERO(zds, xl);
 
@@ -1713,8 +1717,6 @@ rb_big_mul_balance(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L1717
 {
     size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
     VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
-    if (!(2 * xn <= yn || 3 * xn <= 2*(yn+2)))
-        rb_raise(rb_eArgError, "invalid bignum length");
     bary_mul_balance_with_mulfunc(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0, bary_mul_toom3_start);
     RB_GC_GUARD(x);
     RB_GC_GUARD(y);
@@ -1895,8 +1897,8 @@ rb_big_mul_karatsuba(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L1897
 {
     size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
     VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
-    if (!(xn <= yn && yn < 2 * xn))
-        rb_raise(rb_eArgError, "invalid bignum length");
+    if (!(xn <= yn && yn < 2 || KARATSUBA_BALANCED(xn, yn)))
+        rb_raise(rb_eArgError, "unexpected bignum length for karatsuba");
     bary_mul_karatsuba(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
     RB_GC_GUARD(x);
     RB_GC_GUARD(y);
@@ -2299,8 +2301,8 @@ rb_big_mul_toom3(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L2301
 {
     size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn;
     VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
-    if (xn > yn || yn < 3 || !((yn+2)/3 * 2 < xn))
-        rb_raise(rb_eArgError, "invalid bignum length");
+    if (xn > yn || yn < 3 || !TOOM3_BALANCED(xn,yn))
+        rb_raise(rb_eArgError, "unexpected bignum length for toom3");
     bary_mul_toom3(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, NULL, 0);
     RB_GC_GUARD(x);
     RB_GC_GUARD(y);
@@ -2453,7 +2455,7 @@ bary_mul_karatsuba_branch(BDIGIT *zds, s https://github.com/ruby/ruby/blob/trunk/bignum.c#L2455
     }
 
     /* balance multiplication by slicing y when x is much smaller than y */
-    if (2 * xl <= yl) {
+    if (!KARATSUBA_BALANCED(xl, yl)) {
         bary_mul_balance_with_mulfunc(zds, zl, xds, xl, yds, yl, wds, wl, bary_mul_karatsuba_start);
         return;
     }
@@ -2479,7 +2481,7 @@ bary_mul_toom3_branch(BDIGIT *zds, size_ https://github.com/ruby/ruby/blob/trunk/bignum.c#L2481
         return;
     }
 
-    if (3*xl <= 2*(yl + 2)) {
+    if (!TOOM3_BALANCED(xl, yl)) {
         bary_mul_balance_with_mulfunc(zds, zl, xds, xl, yds, yl, wds, wl, bary_mul_toom3_start);
         return;
     }

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

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