From: TOYOFUKU Chikanobu <nobu_toyofuku@...>
Date: 2008-09-01T20:37:43+09:00
Subject: [ruby-dev:36080] optimize bigdivrem Part 2

  豊福です。

  前回と同様に divp と modp に関する節約です。

気になること。
・「while (!yds[ny-1]) ny--;」はいらないような気がするのですが
   取りあえず位置を先頭に移動して残しておきました。
   x と y は normalize されてないことがあるんでしょうか？
   そもそも ny を信用できないなら最初の
      if (nx < ny || ...
   からしてまずいと思うのですが。
・z を必ず divp と modp のどちらかで使えば宣言の volatile も
  いらなくなる？

もろもろ自信ないので検証お願いします。

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

---