From c0cce2938c4e19508d1cd6412889c669da04cd7b Mon Sep 17 00:00:00 2001 From: akr Date: Tue, 16 Jul 2013 09:37:42 +0000 Subject: * 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 --- ChangeLog | 6 ++++++ bignum.c | 28 +++++++++++++++++++++------- 2 files changed, 27 insertions(+), 7 deletions(-) diff --git a/ChangeLog b/ChangeLog index de57946ddd..5e957fc9b1 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +Tue Jul 16 18:35:48 2013 Tanaka Akira + + * bignum.c (bary_mul_karatsuba): Avoid duplicate calculation when + squaring. + ((bary_mul_toom3_branch): Ditto. + Tue Jul 16 17:43:22 2013 Koichi Sasada * gc.c (link_free_heap_slot): removed. diff --git a/bignum.c b/bignum.c index 5fac60cdda..3a03f1bbfc 100644 --- a/bignum.c +++ b/bignum.c @@ -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)); -- cgit v1.2.3