akr	2013-07-16 18:37:42 +0900 (Tue, 16 Jul 2013)

  New Revision: 42001

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

  Log:
    * bignum.c (bary_mul_karatsuba): Avoid duplicate calculation when
      squaring.
      ((bary_mul_toom3_branch): Ditto.

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 42000)
+++ ChangeLog	(revision 42001)
@@ -1,3 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Tue Jul 16 18:35:48 2013  Tanaka Akira  <akr@f...>
+
+	* bignum.c (bary_mul_karatsuba): Avoid duplicate calculation when
+	  squaring.
+	  ((bary_mul_toom3_branch): Ditto.
+
 Tue Jul 16 17:43:22 2013  Koichi Sasada  <ko1@a...>
 
 	* gc.c (link_free_heap_slot): removed.
Index: bignum.c
===================================================================
--- bignum.c	(revision 42000)
+++ bignum.c	(revision 42001)
@@ -1704,6 +1704,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t z https://github.com/ruby/ruby/blob/trunk/bignum.c#L1704
 
     int odd_y = 0;
     int odd_xy = 0;
+    int sq;
 
     BDIGIT *xds0, *xds1, *yds0, *yds1, *zds0, *zds1, *zds2, *zds3;
 
@@ -1711,6 +1712,8 @@ bary_mul_karatsuba(BDIGIT *zds, size_t z https://github.com/ruby/ruby/blob/trunk/bignum.c#L1712
     assert(xl <= yl);
     assert(yl < 2 * xl);
 
+    sq = xds == yds && xl == yl;
+
     if (yl & 1) {
         odd_y = 1;
         yl--;
@@ -1766,14 +1769,20 @@ bary_mul_karatsuba(BDIGIT *zds, size_t z https://github.com/ruby/ruby/blob/trunk/bignum.c#L1769
 
     /* zds0:|x1-x0| zds1:? zds2:? zds3:? wds:? */
 
-    if (bary_sub(wds, n, yds, n, yds+n, n)) {
-        bary_2comp(wds, n);
-        sub_p = !sub_p;
+    if (sq) {
+        sub_p = 1;
+        bary_mul_karatsuba_start(zds1, 2*n, zds0, n, zds0, n, wds, wl);
     }
+    else {
+        if (bary_sub(wds, n, yds, n, yds+n, n)) {
+            bary_2comp(wds, n);
+            sub_p = !sub_p;
+        }
 
-    /* zds0:|x1-x0| zds1:? zds2:? zds3:? wds:|y1-y0| */
+        /* zds0:|x1-x0| zds1:? zds2:? zds3:? wds:|y1-y0| */
 
-    bary_mul_karatsuba_start(zds1, 2*n, zds0, n, wds, n, wds+n, wl-n);
+        bary_mul_karatsuba_start(zds1, 2*n, zds0, n, wds, n, wds+n, wl-n);
+    }
 
     /* zds0:|x1-x0| zds1,zds2:|x1-x0|*|y1-y0| zds3:? wds:|y1-y0| */
 
@@ -2029,8 +2038,13 @@ bary_mul_toom3_branch(BDIGIT *zds, size_ https://github.com/ruby/ruby/blob/trunk/bignum.c#L2038
         VALUE x, y, z;
         x = bignew(xl, 1);
 	MEMCPY(BDIGITS(x), xds, BDIGIT, xl);
-        y = bignew(yl, 1);
-	MEMCPY(BDIGITS(y), yds, BDIGIT, yl);
+        if (xds == yds && xl == yl) {
+            y = x;
+        }
+        else {
+            y = bignew(yl, 1);
+            MEMCPY(BDIGITS(y), yds, BDIGIT, yl);
+        }
         z = bigtrunc(bigmul1_toom3(x, y));
         MEMCPY(zds, BDIGITS(z), BDIGIT, RBIGNUM_LEN(z));
         MEMZERO(zds + RBIGNUM_LEN(z), BDIGIT, zl - RBIGNUM_LEN(z));

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