akr	2013-07-08 20:56:55 +0900 (Mon, 08 Jul 2013)

  New Revision: 41830

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

  Log:
    * bignum.c (bary_mul_balance): Reduce work memory.

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c
    trunk/test/-ext-/bignum/test_mul.rb

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 41829)
+++ ChangeLog	(revision 41830)
@@ -1,3 +1,7 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Mon Jul  8 20:55:22 2013  Tanaka Akira  <akr@f...>
+
+	* bignum.c (bary_mul_balance): Reduce work memory.
+
 Mon Jul  8 08:26:15 2013  Martin Bosslet  <Martin.Bosslet@g...>
 
 	* test/openssl/test_pkey_ec.rb: Skip tests for "Oakley" curves as
Index: bignum.c
===================================================================
--- bignum.c	(revision 41829)
+++ bignum.c	(revision 41830)
@@ -1542,28 +1542,46 @@ static void https://github.com/ruby/ruby/blob/trunk/bignum.c#L1542
 bary_mul_balance(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl)
 {
     VALUE work = 0;
-    size_t r, n;
     BDIGIT *wds;
-    size_t wl;
+    size_t yl0 = yl;
+    size_t r, n;
+    size_t wl = 0;
 
     assert(xl + yl <= zl);
     assert(2 * xl <= yl || 3 * xl <= 2*(yl+2));
 
-    wl = xl * 2;
-    wds = ALLOCV_N(BDIGIT, work, wl);
-
-    MEMZERO(zds, BDIGIT, zl);
+    MEMZERO(zds, BDIGIT, xl);
 
     n = 0;
     while (yl > 0) {
+        BDIGIT *tds;
+        size_t tl;
 	r = xl > yl ? yl : xl;
-        bary_mul(wds, xl + r, xds, xl, yds + n, r);
-        bary_add(zds + n, zl - n,
-                 zds + n, zl - n,
-                 wds, xl + r);
+        tl = xl + r;
+        if (2 * (xl + r) <= zl - n) {
+            tds = zds + n + xl + r;
+            bary_mul(tds, tl, xds, xl, yds + n, r);
+            MEMZERO(zds + n + xl, BDIGIT, r);
+            bary_add(zds + n, tl,
+                     zds + n, tl,
+                     tds, tl);
+        }
+        else {
+            if (wl < xl) {
+                wl = xl;
+                wds = ALLOCV_N(BDIGIT, work, wl);
+            }
+            tds = zds + n;
+            MEMCPY(wds, zds + n, BDIGIT, xl);
+            bary_mul(tds, tl, xds, xl, yds + n, r);
+            bary_add(zds + n, tl,
+                     zds + n, tl,
+                     wds, xl);
+        }
 	yl -= r;
 	n += r;
     }
+    MEMZERO(zds+xl+yl0, BDIGIT, zl - (xl+yl0));
 
     if (work)
         ALLOCV_END(work);
Index: test/-ext-/bignum/test_mul.rb
===================================================================
--- test/-ext-/bignum/test_mul.rb	(revision 41829)
+++ test/-ext-/bignum/test_mul.rb	(revision 41830)
@@ -43,6 +43,18 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/-ext-/bignum/test_mul.rb#L43
       assert_equal(z, x.big_mul_balance(y))
     end
 
+    def test_mul_balance_2x16
+      x = (1 << Bignum::BITSPERDIG) | 1
+      y = (1 << Bignum::BITSPERDIG*16) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_balance(y))
+    end
+
+    def test_mul_balance_2x17
+      x = (1 << Bignum::BITSPERDIG) | 1
+      y = (1 << Bignum::BITSPERDIG*17) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_balance(y))
+    end
+
     def test_mul_karatsuba
       x = (1 << BITSPERDIG) | 1
       y = (1 << BITSPERDIG) | 1

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