ruby-changes:30071
From: akr <ko1@a...>
Date: Tue, 23 Jul 2013 07:16:56 +0900 (JST)
Subject: [ruby-changes:30071] akr:r42123 (trunk): * bignum.c (bary_mulsub_1xN): New function.
akr 2013-07-23 07:16:45 +0900 (Tue, 23 Jul 2013) New Revision: 42123 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42123 Log: * bignum.c (bary_mulsub_1xN): New function. (bary_mul_toom3): Use bary_mulsub_1xN. Modified files: trunk/ChangeLog trunk/bignum.c Index: ChangeLog =================================================================== --- ChangeLog (revision 42122) +++ ChangeLog (revision 42123) @@ -1,3 +1,8 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Tue Jul 23 07:14:31 2013 Tanaka Akira <akr@f...> + + * bignum.c (bary_mulsub_1xN): New function. + (bary_mul_toom3): Use bary_mulsub_1xN. + Tue Jul 23 03:32:23 2013 Tanaka Akira <akr@f...> * bignum.c (KARATSUBA_BALANCED): New macro. Index: bignum.c =================================================================== --- bignum.c (revision 42122) +++ bignum.c (revision 42123) @@ -1571,6 +1571,46 @@ bary_muladd_1xN(BDIGIT *zds, size_t zl, https://github.com/ruby/ruby/blob/trunk/bignum.c#L1571 return n != 0; } +static BDIGIT_DBL_SIGNED +bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn) +{ + size_t i; + BDIGIT_DBL t2; + BDIGIT_DBL_SIGNED num; + + assert(zn == yn + 1); + + num = 0; + t2 = 0; + i = 0; + + do { + BDIGIT_DBL ee; + t2 += (BDIGIT_DBL)yds[i] * x; + ee = num - BIGLO(t2); + num = (BDIGIT_DBL)zds[i] + ee; + if (ee) zds[i] = BIGLO(num); + num = BIGDN(num); + t2 = BIGDN(t2); + } while (++i < yn); + num += zds[i] - t2; /* borrow from high digit; don't update */ + return num; +} + +static int +bary_mulsub_1xN(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn) +{ + BDIGIT_DBL_SIGNED num; + + assert(zn == yn + 1); + + num = bigdivrem_mulsub(zds, zn, x, yds, yn); + zds[yn] = BIGLO(num); + if (BIGDN(num)) + return 1; + return 0; +} + static void bary_mul_normal(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds, size_t yl) { @@ -2222,11 +2262,7 @@ bary_mul_toom3(BDIGIT *zds, size_t zn, B https://github.com/ruby/ruby/blob/trunk/bignum.c#L2262 bary_muladd_1xN(z3ds, z3n, 2, t4ds, t4n); } else { - /* TODO: combining with next addition */ - t1ds[t4n] = bary_small_lshift(t1ds, t4ds, t4n, 1); - t1n = t4n+1; - t1p = t4p; - if (bary_sub(z3ds, z3n, z3ds, z3n, t1ds, t1n)) { + if (bary_mulsub_1xN(z3ds, z3n, 2, t4ds, t4n)) { bary_2comp(z3ds, z3n); z3p = !z3p; } @@ -5102,32 +5138,6 @@ struct big_div_struct { https://github.com/ruby/ruby/blob/trunk/bignum.c#L5138 volatile VALUE stop; }; -static BDIGIT_DBL_SIGNED -bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT *yds, size_t yn) -{ - size_t i; - BDIGIT_DBL t2; - BDIGIT_DBL_SIGNED num; - - assert(zn == yn + 1); - - num = 0; - t2 = 0; - i = 0; - - do { - BDIGIT_DBL ee; - t2 += (BDIGIT_DBL)yds[i] * x; - ee = num - BIGLO(t2); - num = (BDIGIT_DBL)zds[i] + ee; - if (ee) zds[i] = BIGLO(num); - num = BIGDN(num); - t2 = BIGDN(t2); - } while (++i < yn); - num += zds[i] - t2; /* borrow from high digit; don't update */ - return num; -} - static void * bigdivrem1(void *ptr) { -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/