From: Nobuyoshi Nakada <nobu@...>
Date: 2007-04-26T23:11:16+09:00
Subject: [ruby-dev:30734] Re: 累乗が遅い

なかだです。

At Thu, 26 Apr 2007 20:34:23 +0900,
Kouhei Yanagita wrote in [ruby-dev:30733]:
> -------------------
> r10898 | matz | 2006-09-10 00:27:34 +0900 (日, 10  9月 2006) | 5 lines
> 
> * bignum.c (rb_big_mul0): bignum multiplication without
>   normalization.
> 
> * bignum.c (rb_big_pow): use rb_big_mul0().  [ruby-dev:29547]
> -------------------
> 
> ここから遅くなっているようです。

こっちが問題のようです。要するに

> * bignum.c (rb_big_pow): eagerly truncate resulting bignum.

は、一桁だけでは足りないということっぽいですね。

これでようやくruby版とトントンかやや速い程度になりました。


Index: bignum.c
===================================================================
--- bignum.c	(revision 12216)
+++ bignum.c	(working copy)
@@ -91,26 +91,31 @@ rb_big_2comp(VALUE x)			/* get 2's compl
 
 static VALUE
-bignorm(VALUE x)
+bigtrunc(VALUE x)
 {
-    if (FIXNUM_P(x)) {
-	return x;
-    }
-    else if (TYPE(x) == T_BIGNUM) {
-	long len = RBIGNUM(x)->len;
-	BDIGIT *ds = BDIGITS(x);
-
-	while (len-- && !ds[len]) ;
-	RBIGNUM(x)->len = ++len;
-
-	if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) {
-	    SIGNED_VALUE num = 0;
-	    while (len--) {
-		num = BIGUP(num) + ds[len];
+    long len = RBIGNUM(x)->len;
+    BDIGIT *ds = BDIGITS(x);
+
+    while (len-- && !ds[len]);
+    RBIGNUM(x)->len = ++len;
+    return x;
+}
+
+static VALUE
+bigfixize(VALUE x)
+{
+    long len = RBIGNUM(x)->len;
+    BDIGIT *ds = BDIGITS(x);
+
+    if (len*SIZEOF_BDIGITS <= sizeof(VALUE)) {
+	SIGNED_VALUE 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);
 	    }
 	}
@@ -119,4 +124,13 @@ bignorm(VALUE x)
 }
 
+static VALUE
+bignorm(VALUE x)
+{
+    if (!FIXNUM_P(x) && TYPE(x) == T_BIGNUM) {
+	x = bigfixize(bigtrunc(x));
+    }
+    return x;
+}
+
 VALUE
 rb_big_norm(VALUE x)
@@ -1553,5 +1567,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,14 +1574,12 @@ 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);
-		if (!BDIGITS(z)[RBIGNUM(z)->len-1]) RBIGNUM(z)->len--;
+		    bigtrunc(x);
+		} while (yy % 2 == 0);
+		z = z ? rb_big_mul0(z, x) : x;
+		bigtrunc(z);
 	    }
 	    return bignorm(z);


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