$BN_>h$,CY$$(B

Ruby Development
1

e$B$J$+$@$G$9!#e(B

http://yowaken.dip.jp/tdiary/20070425.html#p02 e$B$K$“$k$h$&$K3N$+e(B
e$B$KN_>h$,CY$$$h$&$G$9!#e(BFixnume$B$G=<J,$J1i;;$be(BBignume$B$s$G9T$C$F$$$ke(B
e$B$N$,Bg$-$$$h$&$G$9$,!”$=$l$@$1$G$b$J$$$h$&$G!"$3$l$G$b$^$@e(Bruby
e$BHG$h$j>/!9CY$$$h$&$G$9!#e(B

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));
2

e$B$J$+$@$G$9!#e(B

At Thu, 26 Apr 2007 13:12:48 +0900,
Nobuyoshi N. wrote in [ruby-dev:30726]:

+static VALUE
+int_pow(long x, unsigned long y)
+{

  • int sign = x < 0;
  • long z = 1;
  • if (sign) x = -x;

e$BId9f$rLa$9$N$rK:$l$F$^$7$?!#e(B

  •  if (x2 < x || !POSFIXABLE(x2)) {

  •    bignum:
  • return rb_big_mul(rb_big_pow(rb_int2big(x), LONG2NUM(y)),
  •      rb_int2big(sign ? -z : z));
  • } while (–y);
  • if (sign) z = -z;
3

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:30726] e$BN_>h$,CY$$e(B”
on Thu, 26 Apr 2007 13:12:48 +0900, Nobuyoshi N.
[email protected] writes:
|
|e$B$J$+$@$G$9!#e(B
|
|http://yowaken.dip.jp/tdiary/20070425.html#p02 e$B$K$“$k$h$&$K3N$+e(B
|e$B$KN_>h$,CY$$$h$&$G$9!#e(BFixnume$B$G=<J,$J1i;;$be(BBignume$B$s$G9T$C$F$$$ke(B
|e$B$N$,Bg$-$$$h$&$G$9$,!”$=$l$@$1$G$b$J$$$h$&$G!"$3$l$G$b$^$@e(Bruby
|e$BHG$h$j>/!9CY$$$h$&$G$9!#e(B

e$B$H$j$"$($:e(Btrunke$B$K%3%%C%H$7$F$/$@$5$$!#$,!"$3$l$G$be(BRubye$BHV$he(B
e$B$jM$7$$$C$F$N$O?R>o$8$c$J$$$G$9$M!#$I$&$7$F$J$s$@$m$&!)e(B

4

e$BLxED$G$9!#e(B

1.8.5 e$B$G$OFC$KCY$$$H$$$&$3$H$O$J$/e(B 1.8.6 e$B$G$OCY$+$C$?$N$G!"e(B
ruby_1_8 e$B%V%i%s%A$G$I$3$+$iCY$/$J$C$F$k$+D4$Y$F$_$^$7$?!#e(B

r10880 e$B$N%3%_%C%He(B

r10880 | matz | 2006-09-08 01:35:59 +0900 (e$B6be(B, 08 9e$B7ne(B 2006)
| 9 lines

  • numeric.c (fix_plus): addition in Fixnum will never overflow
    long. a patch from Ondrej B. .
    [ruby-core:08794]

  • numeric.c (fix_minus): ditto.

  • bignum.c (rb_big_pow): eagerly truncate resulting bignum.
    [ruby-core:08794]

e$B$G!"N_>h$,e(B core dump e$B$9$k$h$&$K$J$C$F$$$^$9!#e(B
e$B$3$ND>A0$^$G$O!“LdBj$”$j$^$;$s$G$7$?!#e(B

e$B$3$Ne(B core dump e$B$r=$@5$7$?e(B

r10898 | matz | 2006-09-10 00:27:34 +0900 (e$BF|e(B, 10 9e$B7ne(B 2006)
| 5 lines

  • bignum.c (rb_big_mul0): bignum multiplication without
    normalization.

  • bignum.c (rb_big_pow): use rb_big_mul0(). [ruby-dev:29547]

e$B$3$3$+$iCY$/$J$C$F$$$k$h$&$G$9!#e(B

5

e$B$^$D$b$He(B e$B$f$-$R$m$G$9e(B

In message “Re: [ruby-dev:30734] Re: e$BN_>h$,CY$$e(B”
on Thu, 26 Apr 2007 23:11:16 +0900, Nobuyoshi N.
[email protected] writes:

|> * bignum.c (rb_big_pow): use rb_big_mul0(). [ruby-dev:29547]
|> -------------------
|>
|> e$B$3$3$+$iCY$/$J$C$F$$$k$h$&$G$9!#e(B
|
|e$B$3$C$A$,LdBj$N$h$&$G$9!#MW$9$k$Ke(B
|
|> * bignum.c (rb_big_pow): eagerly truncate resulting bignum.
|
|e$B$O!"0l7e$@$1$G$OB-$j$J$$$H$$$&$3$H$C$]$$$G$9$M!#e(B

e$B$9$$$^$;$s!"$d$C$Q$j;d$N$;$$$G$7$?$M!#e(B

|e$B$3$l$G$h$&$d$/e(Brubye$BHG$H%H%s%H%s$+$d$dB.$$DxEY$K$J$j$^$7$?!#e(B

e$B%3%_%C%H$7$F$/$@$5$$!#$7$+$7!"$^$@CY$$$N$M!#e(B

6

e$B$J$+$@$G$9!#e(B

At Thu, 26 Apr 2007 20:34:23 +0900,
Kouhei Y. wrote in [ruby-dev:30733]:

r10898 | matz | 2006-09-10 00:27:34 +0900 (e$BF|e(B, 10 9e$B7ne(B 2006) | 5 lines

  • bignum.c (rb_big_mul0): bignum multiplication without
    normalization.

  • bignum.c (rb_big_pow): use rb_big_mul0(). [ruby-dev:29547]

e$B$3$3$+$iCY$/$J$C$F$$$k$h$&$G$9!#e(B

e$B$3$C$A$,LdBj$N$h$&$G$9!#MW$9$k$Ke(B

  • bignum.c (rb_big_pow): eagerly truncate resulting bignum.

e$B$O!"0l7e$@$1$G$OB-$j$J$$$H$$$&$3$H$C$]$$$G$9$M!#e(B

e$B$3$l$G$h$&$d$/e(Brubye$BHG$H%H%s%H%s$+$d$dB.$$DxEY$K$J$j$^$7$?!#e(B

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);