diff options
| -rw-r--r-- | ChangeLog | 7 | ||||
| -rw-r--r-- | bignum.c | 12 | ||||
| -rw-r--r-- | numeric.c | 34 |
3 files changed, 45 insertions, 8 deletions
@@ -1,3 +1,10 @@ +Thu Apr 26 17:31:00 2007 Nobuyoshi Nakada <nobu@ruby-lang.org> + + * bignum.c (rb_big_pow): reduce multiplying for even number. + + * numeric.c (int_pow): calculate power in Fixnum as possible. + [ruby-dev:30726] + Thu Apr 26 17:18:51 2007 Nobuyoshi Nakada <nobu@ruby-lang.org> * parse.y: fixes for ripper. @@ -1552,22 +1552,20 @@ rb_big_pow(VALUE x, VALUE y) case T_FIXNUM: yy = FIX2LONG(y); if (yy > 0) { - VALUE z = x; + VALUE z = (yy & 1) ? x : 0; 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) { + while (yy &= ~1) { + do { yy /= 2; x = rb_big_mul0(x, x); if (!BDIGITS(x)[RBIGNUM(x)->len-1]) RBIGNUM(x)->len--; - } - z = rb_big_mul0(z, x); + } while (yy % 2 == 0); + z = z ? rb_big_mul0(z, x) : x; if (!BDIGITS(z)[RBIGNUM(z)->len-1]) RBIGNUM(z)->len--; } return bignorm(z); @@ -2259,6 +2259,38 @@ fix_divmod(VALUE x, VALUE y) } } +static VALUE +int_pow(long x, unsigned long y) +{ + int neg = x < 0; + long z = 1; + + if (neg) x = -x; + if (y & 1) z = x; + y &= ~1; + do { + while (y % 2 == 0) { + long x2 = x * x; + if (x2 < x || !POSFIXABLE(x2)) { + bignum: + return rb_big_mul(rb_big_pow(rb_int2big(x), LONG2NUM(y)), + rb_int2big(neg ? -z : z)); + } + x = x2; + y >>= 1; + } + { + long xz = x * z; + if (xz < z || xz < x || !POSFIXABLE(xz)) { + goto bignum; + } + z = xz; + } + } while (--y); + if (neg) z = -z; + return LONG2NUM(z); +} + /* * call-seq: * fix ** other => Numeric @@ -2282,7 +2314,7 @@ fix_pow(VALUE x, VALUE y) if (b == 1) return x; a = FIX2LONG(x); if (b > 0) { - return rb_big_pow(rb_int2big(a), y); + return int_pow(a, b); } return rb_float_new(pow((double)a, (double)b)); } |