# 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

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

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) {
``````

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

TOYOFUKU Chikanobu wrote: