diff options
author | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2007-05-09 02:50:04 +0000 |
---|---|---|
committer | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2007-05-09 02:50:04 +0000 |
commit | 952e281a2ae3b2d7fd4d7914a034985383e09ce9 (patch) | |
tree | 77b0284e7fc23d8620aa8b8bf8838df8f5ead250 | |
parent | 84eb18a91f81280e3e37e46486871237b80540f1 (diff) |
* bignum.c (rb_big_pow): reduce multiplying for even number.
* bignum.c (rb_big_pow): truncate all zero BDIGITs. [ruby-dev:30733]
* bignum.c (rb_big_pow): improvement by calculating from MSB and using
factorization. <http://yowaken.dip.jp/tdiary/20070426.html#p01>
* numeric.c (int_pow): calculate power in Fixnum as possible.
[ruby-dev:30726]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_8@12260 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 12 | ||||
-rw-r--r-- | bignum.c | 126 |
2 files changed, 109 insertions, 29 deletions
@@ -1,3 +1,15 @@ +Wed May 9 11:51:06 2007 Nobuyoshi Nakada <nobu@ruby-lang.org> + + * bignum.c (rb_big_pow): reduce multiplying for even number. + + * bignum.c (rb_big_pow): truncate all zero BDIGITs. [ruby-dev:30733] + + * bignum.c (rb_big_pow): improvement by calculating from MSB and using + factorization. <http://yowaken.dip.jp/tdiary/20070426.html#p01> + + * numeric.c (int_pow): calculate power in Fixnum as possible. + [ruby-dev:30726] + Tue May 8 23:42:51 2007 Tadayoshi Funaba <tadf@dotrb.org> * lib/date/format.rb (Date._parse): revised treatment of @@ -96,35 +96,51 @@ rb_big_2comp(x) /* get 2's complement */ } static VALUE -bignorm(x) +bigtrunc(x) VALUE x; { - if (FIXNUM_P(x)) { - return x; - } - else if (TYPE(x) == T_BIGNUM) { - long len = RBIGNUM(x)->len; - BDIGIT *ds = BDIGITS(x); + long len = RBIGNUM(x)->len; + BDIGIT *ds = BDIGITS(x); - while (len-- && !ds[len]) ; - RBIGNUM(x)->len = ++len; + while (len-- && !ds[len]); + RBIGNUM(x)->len = ++len; + return x; +} - if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) { - long num = 0; - while (len--) { - num = BIGUP(num) + ds[len]; +static VALUE +bigfixize(x) + VALUE x; +{ + long len = RBIGNUM(x)->len; + BDIGIT *ds = BDIGITS(x); + + if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) { + long num = 0; + while (len--) { + num = BIGUP(num) + ds[len]; + } + if (num >= 0) { + if (RBIGNUM(x)->sign) { + if (POSFIXABLE(num)) return LONG2FIX(num); } - if (num >= 0) { - if (RBIGNUM(x)->sign) { - if (POSFIXABLE(num)) return LONG2FIX(num); - } - else if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(long)num); + else { + if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(long)num); } } } return x; } +static VALUE +bignorm(x) + VALUE x; +{ + if (!FIXNUM_P(x) && TYPE(x) == T_BIGNUM) { + x = bigfixize(bigtrunc(x)); + } + return x; +} + VALUE rb_big_norm(x) VALUE x; @@ -1594,6 +1610,50 @@ rb_big_quo(x, y) return rb_float_new(dx / dy); } +static VALUE +bigsqr(x) + VALUE x; +{ + long len = RBIGNUM(x)->len, k = len / 2, i; + VALUE a, b, a2, z; + BDIGIT_DBL num; + + if (len < 4000 / BITSPERDIG) { + return rb_big_mul0(x, x); + } + + a = bignew(len - k, 1); + MEMCPY(BDIGITS(a), BDIGITS(x) + k, BDIGIT, len - k); + b = bignew(k, 1); + MEMCPY(BDIGITS(b), BDIGITS(x), BDIGIT, k); + + a2 = bigtrunc(bigsqr(a)); + z = bigsqr(b); + REALLOC_N(RBIGNUM(z)->digits, BDIGIT, (len = 2 * k + RBIGNUM(a2)->len) + 1); + while (RBIGNUM(z)->len < 2 * k) BDIGITS(z)[RBIGNUM(z)->len++] = 0; + MEMCPY(BDIGITS(z) + 2 * k, BDIGITS(a2), BDIGIT, RBIGNUM(a2)->len); + RBIGNUM(z)->len = len; + a2 = bigtrunc(rb_big_mul0(a, b)); + len = RBIGNUM(a2)->len; + for (i = 0, num = 0; i < len; i++) { + num += (BDIGIT_DBL)BDIGITS(z)[i + k] + ((BDIGIT_DBL)BDIGITS(a2)[i] << 1); + BDIGITS(z)[i + k] = BIGLO(num); + num = BIGDN(num); + } + if (num) { + len = RBIGNUM(z)->len; + for (i += k; i < len && num; ++i) { + num += (BDIGIT_DBL)BDIGITS(z)[i]; + BDIGITS(z)[i] = BIGLO(num); + num = BIGDN(num); + } + if (num) { + BDIGITS(z)[RBIGNUM(z)->len++] = BIGLO(num); + } + } + return bigtrunc(z); +} + /* * call-seq: * big ** exponent #=> numeric @@ -1613,7 +1673,7 @@ rb_big_pow(x, y) { double d; long yy; - + if (y == INT2FIX(0)) return INT2FIX(1); switch (TYPE(y)) { case T_FLOAT: @@ -1628,23 +1688,31 @@ rb_big_pow(x, y) case T_FIXNUM: yy = FIX2LONG(y); if (yy > 0) { - VALUE z = x; + VALUE z = 0; + long mask, n = 1; if (RBIGNUM(x)->len * SIZEOF_BDIGITS * yy > 1024*1024) { rb_warn("in a**b, b may be too big"); d = (double)yy; break; } - for (;;) { - yy -= 1; - if (yy == 0) break; - while (yy % 2 == 0) { - yy /= 2; - x = rb_big_mul0(x, x); - if (!BDIGITS(x)[RBIGNUM(x)->len-1]) RBIGNUM(x)->len--; + for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) { + if (!z) { + long n2 = n * n; + if (!POSFIXABLE(n2) || (n2 / n != n)) { + z = bigtrunc(bigsqr(rb_int2big(n))); + } + else { + n = n2; + } + } + else { + z = bigtrunc(bigsqr(z)); + } + if (yy & mask) { + if (!z) z = rb_int2big(n); + z = bigtrunc(rb_big_mul0(z, x)); } - z = rb_big_mul0(z, x); - if (!BDIGITS(z)[RBIGNUM(z)->len-1]) RBIGNUM(z)->len--; } return bignorm(z); } |