Optimize bigdivrem Part 1

TOYOFUKU_Chikanobu · September 1, 2008, 11:43am

e$BK-J!$G$9!#e(B

e$B$$$/$D$+e(B bigdivrem e$B$N:GE,2=0F$,$"$j$^$9!#e(B
e$B$^$:$O8!>Z$,0lHV4JC1$=$&$J$d$D$+$ie(B

— bignum.c.org
+++ bignum.c
@@ -1693,20 +1693,27 @@
xds = BDIGITS(x);
if (ny == 1) {
dd = yds[0];

```
  z = rb_big_clone(x);
```
```
  zds = BDIGITS(z);
```

```
  if (divp) {
```
```
      z = rb_big_clone(x);
```
```
      zds = BDIGITS(z);
```
```
  }
  t2 = 0; i = nx;
  while (i--) {
```

```
      t2 = BIGUP(t2) + zds[i];
```
```
      zds[i] = (BDIGIT)(t2 / dd);
```

```
      t2 = BIGUP(t2) + xds[i];
```
```
      q = (BDIGIT)(t2 / dd);
```

      if (divp) zds[i] = q;
      t2 %= dd;
  }

  RBIGNUM_SET_SIGN(z, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));

```
  if (divp) {
```
```
      while (--nx && !zds[nx]); ++nx;
```
```
      RBIGNUM_SET_LEN(z, nx);
```

      RBIGNUM_SET_SIGN(z, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));

```
      *divp = z;
```

  }
  if (modp) {
      *modp = rb_uint2big((VALUE)t2);
      RBIGNUM_SET_SIGN(*modp, RBIGNUM_SIGN(x));
  }

```
  if (divp) *divp = z;
  return Qnil;
```
}
z = bignew(nx==ny?nx+2:nx+1, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));

TOYOFUKU_Chikanobu · September 1, 2008, 12:12pm

e$BK-J!$G$9!#e(B

```
      while (--nx && !zds[nx]); ++nx;
```
```
      RBIGNUM_SET_LEN(z, nx);
```

e$B8e$Ge(B bignorm e$B$5$l$k$N$G$3$N#29T$O$$$j$^$;$s$G$7$?!#e(B

TOYOFUKU_Chikanobu · September 2, 2008, 11:16am

e$BK-J!$G$9!#e(B

bigdivrem e$B$N7W;;2aDx$G;H$&%*%V%8%'%/%H$N@aLs$G$9!#e(B
e$B@8$Ge(B ALLOC_N e$B$He(B free e$B$r;H$&$N$O$h$/$J$$!)e(B

— bignum.c.org
+++ bignum.c
@@ -1678,8 +1678,8 @@
struct big_div_struct bds;
long nx = RBIGNUM_LEN(x), ny = RBIGNUM_LEN(y), nz;
long i, j;

volatile VALUE yy, z;
BDIGIT *xds, *yds, *zds, *tds;

volatile VALUE z;
BDIGIT *xds, *yds, *zds, *tds = 0;
BDIGIT_DBL t2;
BDIGIT dd, q;

@@ -1729,8 +1729,7 @@
dd++;
}
if (dd) {

```
  yy = rb_big_clone(y);
```
```
  tds = BDIGITS(yy);
```

  tds = ALLOC_N(BDIGIT, ny);
  j = 0;
  t2 = 0;
  while (j<ny) {

@@ -1766,6 +1765,8 @@
bigdivrem1(&bds);
}

if (tds) free(tds);
if (divp) { /* move quotient down in z */
*divp = modp ? rb_big_clone(z): z;
zds = BDIGITS(*divp);

TOYOFUKU_Chikanobu · September 1, 2008, 1:43pm

e$BK-J!$G$9!#e(B

e$BA02s$HF1MM$Ke(B divp e$B$He(B modp e$B$K4X$9$k@aLs$G$9!#e(B

e$B5$$K$J$k$3$H!#e(B
e$B!&!Ve(Bwhile (!yds[ny-1])
ny–;e$B!W$O$$$i$J$$$h$&$J5$$,$9$k$N$G$9$,e(B
e$B<h$j$“$($:0LCV$r@hF,$K0\F0$7$F;D$7$F$*$-$^$7$?!#e(B
x e$B$He(B y e$B$Oe(B normalize
e$B$5$l$F$J$$$3$H$,$”$k$s$G$7$g$&$+!)e(B
e$B$=$b$=$be(B ny e$B$r?.MQ$G$-$J$$$J$i:G=i$Ne(B
if (nx < ny || …
e$B$+$i$7$F$^$:$$$H;W$&$N$G$9$,!#e(B
e$B!&e(Bz e$B$rI,$:e(B divp e$B$He(B modp e$B$N$I$A$i$+$G;H$($P@k8@$Ne(B
volatile e$B$be(B
e$B$$$i$J$/$J$k!)e(B

e$B$b$m$b$m<+?.$J$$$N$G8!>Z$*4j$$$7$^$9!#e(B

— bignum.c.org
+++ bignum.c
@@ -1676,7 +1676,7 @@
bigdivrem(VALUE x, VALUE y, VALUE *divp, VALUE *modp)
{
struct big_div_struct bds;

long nx = RBIGNUM_LEN(x), ny = RBIGNUM_LEN(y);

long nx = RBIGNUM_LEN(x), ny = RBIGNUM_LEN(y), nz;
long i, j;
volatile VALUE yy, z;
BDIGIT *xds, *yds, *zds, *tds;
@@ -1685,6 +1685,7 @@

if (BIGZEROP(y)) rb_num_zerodiv();
yds = BDIGITS(y);
while (!yds[ny-1]) ny–;
if (nx < ny || (nx == ny && BDIGITS(x)[nx - 1] < BDIGITS(y)[ny -
1])) {
if (divp) *divp = rb_int2big(0);
if (modp) *modp = x;
@@ -1716,10 +1717,10 @@
}
return Qnil;
}

z = bignew(nx==ny?nx+2:nx+1, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));

nz = nx==ny ? nx+2: nx+1;
z = bignew(nz, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
zds = BDIGITS(z);
if (nx==ny) zds[nx+1] = 0;

while (!yds[ny-1]) ny–;

dd = 0;
q = yds[ny-1];
@@ -1766,14 +1767,14 @@
}

if (divp) { /* move quotient down in z */
```
  *divp = rb_big_clone(z);
```

  *divp = modp ? rb_big_clone(z): z;
  zds = BDIGITS(*divp);

```
  j = (nx==ny ? nx+2 : nx+1) - ny;
```

  j = nz - ny;
  for (i = 0;i < j;i++) zds[i] = zds[i+ny];
  RBIGNUM_SET_LEN(*divp, i);

}
if (modp) { /* normalize remainder */

```
  *modp = rb_big_clone(z);
```

  *modp = z;
  zds = BDIGITS(*modp);
  while (--ny && !zds[ny]); ++ny;
  if (dd) {

TOYOFUKU_Chikanobu · September 2, 2008, 11:21am

e$B!!$5$5$@$G$9!%e(B

TOYOFUKU Chikanobu wrote:

bigdivrem e$B$N7W;;2aDx$G;H$&%*%V%8%’%/%H$N@aLs$G$9!#e(B
e$B@8$Ge(B ALLOC_N e$B$He(B free e$B$r;H$&$N$O$h$/$J$$!)e(B

e$B!!>/$J$/$H$b!$e(Bfree e$B$r;H$&$N$O$h$/$J$$$G$9!%e(Bxfree
(ruby_xfree) e$B$r;H$Ce(B
e$B$F$/$@$5$$!%e(B