diff options
author | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-07-16 09:37:42 +0000 |
---|---|---|
committer | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-07-16 09:37:42 +0000 |
commit | c0cce2938c4e19508d1cd6412889c669da04cd7b (patch) | |
tree | f0567df2ee802d8a27b70169bb97989bc1677a01 /bignum.c | |
parent | ed621c001e20b8f6fec152c76360371d8fed38c5 (diff) | |
download | ruby-c0cce2938c4e19508d1cd6412889c669da04cd7b.tar.gz |
* bignum.c (bary_mul_karatsuba): Avoid duplicate calculation when
squaring.
((bary_mul_toom3_branch): Ditto.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42001 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'bignum.c')
-rw-r--r-- | bignum.c | 28 |
1 files changed, 21 insertions, 7 deletions
@@ -1704,6 +1704,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, 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 zl, BDIGIT *xds, size_t xl, BDIGIT *yds, 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 zl, BDIGIT *xds, size_t xl, BDIGIT *yds, /* 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_t zl, BDIGIT *xds, size_t xl, BDIGIT *yd 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)); |