Ruby Forum Ruby-dev > optimize bigdivrem Part 1

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

  $B$$$/$D$+(B bigdivrem $B$N:GE,2=0F$,$"$j$^$9!#(B
$B$^$:$O8!>Z$,0lHV4JC1$=$&$J$d$D$+$i(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));

---

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

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

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

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

  $BA02s$HF1MM$K(B divp $B$H(B modp $B$K4X$9$k@aLs$G$9!#(B

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

$B$b$m$b$m<+?.$J$$$N$G8!>Z$*4j$$$7$^$9!#(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) {

---

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

  bigdivrem $B$N7W;;2aDx$G;H$&%*%V%8%'%/%H$N@aLs$G$9!#(B
$B@8$G(B ALLOC_N $B$H(B free $B$r;H$&$N$O$h$/$J$$!)(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);

---

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

TOYOFUKU Chikanobu wrote:
>   bigdivrem $B$N7W;;2aDx$G;H$&%*%V%8%'%/%H$N@aLs$G$9!#(B
> $B@8$G(B ALLOC_N $B$H(B free $B$r;H$&$N$O$h$/$J$$!)(B

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