diff options
author | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-07-08 11:56:55 +0000 |
---|---|---|
committer | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-07-08 11:56:55 +0000 |
commit | ffe55cdc1e2b18ff5f45b556043eecd672675ec6 (patch) | |
tree | f5694aa74d06743441ed23dcf170d12edace152c | |
parent | ed92ae818f7b14690c401e07c1bdaa0746972cb5 (diff) | |
download | ruby-ffe55cdc1e2b18ff5f45b556043eecd672675ec6.tar.gz |
* bignum.c (bary_mul_balance): Reduce work memory.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41830 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 4 | ||||
-rw-r--r-- | bignum.c | 38 | ||||
-rw-r--r-- | test/-ext-/bignum/test_mul.rb | 12 |
3 files changed, 44 insertions, 10 deletions
@@ -1,3 +1,7 @@ +Mon Jul 8 20:55:22 2013 Tanaka Akira <akr@fsij.org> + + * bignum.c (bary_mul_balance): Reduce work memory. + Mon Jul 8 08:26:15 2013 Martin Bosslet <Martin.Bosslet@gmail.com> * test/openssl/test_pkey_ec.rb: Skip tests for "Oakley" curves as @@ -1542,28 +1542,46 @@ static void 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); diff --git a/test/-ext-/bignum/test_mul.rb b/test/-ext-/bignum/test_mul.rb index 539b9cf138..e125401664 100644 --- a/test/-ext-/bignum/test_mul.rb +++ b/test/-ext-/bignum/test_mul.rb @@ -43,6 +43,18 @@ class TestBignum < Test::Unit::TestCase 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 |