Optimize bigdivrem Part 1

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

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

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

bigdivrem e$B$N7W;;2aDx$G;H$&%*%V%8%’%/%[email protected]$G$9!#e(B
[email protected]$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);

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

e$BA02s$HF1MM$Ke(B divp e$B$He(B modp [email protected]$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$"$($:[email protected],$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$([email protected]@$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) {
    

[email protected]$G$9!%e(B

TOYOFUKU Chikanobu wrote:

bigdivrem e$B$N7W;;2aDx$G;H$&%*%V%8%’%/%[email protected]$G$9!#e(B
[email protected]$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$/[email protected]$5$$!%e(B

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs