# Optimize bigdivrem Part 1

**URL:** <https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393>\
**Category:** Development\
**Created:** [September 1, 2008, 11:43am UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393 "2008-09-01T11:43:54Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [September 1, 2008, 11:43am UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393/1 "2008-09-01T11:43:54Z")

</div>

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](http://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));

* * *

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [September 1, 2008, 12:12pm UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393/2 "2008-09-01T12:12:05Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [September 2, 2008, 11:16am UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393/3 "2008-09-02T11:16:35Z")

</div>

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](http://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);

* * *

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [September 1, 2008, 1:43pm UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393/4 "2008-09-01T13:43:45Z")

</div>

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](http://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 @@

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

- 

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

```

* * *

---

<div class="post-metadata">

**Author:** ![TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/5daacb/32.png) [@TOYOFUKU\_Chikanobu](https://www.ruby-forum.com/u/TOYOFUKU_Chikanobu)\
**Post date:** [September 2, 2008, 11:21am UTC](https://www.ruby-forum.com/t/optimize-bigdivrem-part-1/147393/5 "2008-09-02T11:21:57Z")

</div>

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