[ruby-dev:30734] Re: 累乗が遅い
From:
Nobuyoshi Nakada <nobu@...>
Date:
2007-04-26 14:11:16 UTC
List:
ruby-dev #30734
なかだです。
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はできる。
中田 伸悦