From: Nobuyoshi Nakada <nobu@...>
Date: 2007-04-26T13:12:48+09:00
Subject: [ruby-dev:30726] 累乗が遅い

なかだです。

http://yowaken.dip.jp/tdiary/20070425.html#p02 にあるように確か
に累乗が遅いようです。Fixnumで充分な演算もBignumんで行っている
のが大きいようですが、それだけでもないようで、これでもまだruby
版より少々遅いようです。


Index: bignum.c
===================================================================
--- bignum.c	(revision 12216)
+++ bignum.c	(working copy)
@@ -1553,5 +1553,5 @@ rb_big_pow(VALUE x, VALUE y)
 	yy = FIX2LONG(y);
 	if (yy > 0) {
-	    VALUE z = x;
+	    VALUE z = (yy & 1) ? x : 0;
 
 	    if (RBIGNUM(x)->len * SIZEOF_BDIGITS * yy > 1024*1024) {
@@ -1560,13 +1560,11 @@ rb_big_pow(VALUE x, VALUE y)
 		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--;
 	    }
Index: numeric.c
===================================================================
--- numeric.c	(revision 12216)
+++ numeric.c	(working copy)
@@ -2260,4 +2260,35 @@ fix_divmod(VALUE x, VALUE y)
 }
 
+static VALUE
+int_pow(long x, unsigned long y)
+{
+    int sign = x < 0;
+    long z = 1;
+
+    if (sign) 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(z));
+	    }
+	    x = x2;
+	    y >>= 1;
+	}
+	{
+	    long xz = x * z;
+	    if (xz < z || xz < x || !POSFIXABLE(xz)) {
+		goto bignum;
+	    }
+	    z = xz;
+	}
+    } while (--y);
+    return LONG2NUM(z);
+}
+
 /*
  *  call-seq:
@@ -2283,5 +2314,5 @@ fix_pow(VALUE x, VALUE y)
 	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));


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦