diff options
| -rw-r--r-- | big.c | 65 |
1 files changed, 43 insertions, 22 deletions
@@ -478,48 +478,69 @@ word shortdiv(word x, word n) return q; } -word longdiv(x, y) /* divide big x by big y returning quotient, leaving - remainder in extern variable b_rem */ - /* may assume - x>=0,y>0 */ -word x, y; +/* divide big x by big y returning quotient, leaving + remainder in extern variable b_rem */ +/* may assume - x>=0,y>0 */ +word longdiv(word x, word y) { - word n, q, ly, y1, scale; if (bigcmp(x, y) < 0) { b_rem = x; return (make(INT, 0, 0)); } - y1 = msd(y); - if ((scale = IBASE / (y1 + 1)) > 1) /* rescale if necessary */ - x = stimes(x, scale), y = stimes(y, scale), y1 = msd(y); - n = q = 0; - ly = len(y); - while (bigcmp(x, y = make(INT, 0, y)) >= 0) + + word y1 = msd(y); + + /* rescale if necessary */ + word scale = IBASE / (y1 + 1); + if (scale > 1) { + x = stimes(x, scale); + y = stimes(y, scale); + y1 = msd(y); + } + + word n = 0; + word q = 0; + word ly = len(y); + while (bigcmp(x, y = make(INT, 0, y)) >= 0) { n++; + } + y = rest(y); /* want largest y not exceeding x */ ly += n; for (;;) { word d, lx = len(x); - if (lx < ly) + if (lx < ly) { d = 0; - else if (lx == ly) - if (bigcmp(x, y) >= 0) - x = bigsub(x, y), d = 1; - else + + } else if (lx == ly) { + if (bigcmp(x, y) >= 0) { + x = bigsub(x, y); + d = 1; + } else { d = 0; - else { + } + + } else { d = ms2d(x) / y1; - if (d > MAXDIGIT) + if (d > MAXDIGIT) { d = MAXDIGIT; - if ((d -= 2) > 0) + } + + if ((d -= 2) > 0) { x = bigsub(x, stimes(y, d)); - else + } else { d = 0; + } + if (bigcmp(x, y) >= 0) { x = bigsub(x, y), d++; - if (bigcmp(x, y) >= 0) - x = bigsub(x, y), d++; + if (bigcmp(x, y) >= 0) { + x = bigsub(x, y); + d++; + } } } + q = make(INT, d, q); if (n-- == 0) { b_rem = scale == 1 ? x : shortdiv(x, scale); |