diff options
| -rw-r--r-- | big.c | 87 |
1 files changed, 42 insertions, 45 deletions
@@ -40,11 +40,8 @@ struct big_div { word big_one; -static word shift(word, word); -static word stimes(word, word); - /* no of digits in big x */ -word big__len(word x) +static word big__len(word x) { word n = 1; while ((x = rest(x)) != 0) { @@ -55,7 +52,7 @@ word big__len(word x) } /* most significant digit of big x */ -word big__msd(word x) +static word big__msd(word x) { while (rest(x)) { x = rest(x); @@ -65,7 +62,7 @@ word big__msd(word x) } /* most significant 2 digits of big x (len>=2) */ -word big__ms2d(word x) +static word big__ms2d(word x) { word d = digit(x); x = rest(x); @@ -77,10 +74,42 @@ word big__ms2d(word x) return (digit(x) * IBASE + d); } +/* multiply big x by n'th power of IBASE */ +static word big__shift(word n, word x) +{ + while (n--) { + x = make(INT, 0, x); + } + + return x; +} + +/* multiply big x (>=0) by digit n (>0) */ +static word big__stimes(word x, word n) +{ + unsigned d = n * digit0(x); /* ignore sign of x */ + word carry = d >> DIGITWIDTH; + word r = make(INT, d & MAXDIGIT, 0); + word *y = &rest(r); + + while ((x = rest(x)) != 0) { + d = n * digit(x) + carry; + *y = make(INT, d & MAXDIGIT, 0); + y = &rest(*y); + carry = d >> DIGITWIDTH; + } + + if (carry) { + *y = make(INT, carry, 0); + } + + return r; +} + /* divide big x by single digit n returning big quotient and setting external b_rem as side effect */ /* may assume - x>=0,n>0 */ -struct big_div big__shortdiv(word x, word n) +static struct big_div big__shortdiv(word x, word n) { word d = digit(x); word q = 0; @@ -123,7 +152,7 @@ struct big_div big__shortdiv(word x, word n) /* divide big x by big y returning quotient, leaving remainder in extern variable b_rem */ /* may assume - x>=0,y>0 */ -struct big_div big__longdiv(word x, word y) +static struct big_div big__longdiv(word x, word y) { if (bigcmp(x, y) < 0) { struct big_div bd = { @@ -138,8 +167,8 @@ struct big_div big__longdiv(word x, word y) /* rescale if necessary */ word scale = IBASE / (y1 + 1); if (scale > 1) { - x = stimes(x, scale); - y = stimes(y, scale); + x = big__stimes(x, scale); + y = big__stimes(y, scale); y1 = big__msd(y); } @@ -172,7 +201,7 @@ struct big_div big__longdiv(word x, word y) } if ((d -= 2) > 0) { - x = bigsub(x, stimes(y, d)); + x = bigsub(x, big__stimes(y, d)); } else { d = 0; } @@ -240,7 +269,7 @@ static word big__plus(word x, word y, int signbit) } /* ignore input signs, treat x,y as positive */ -word big__sub(word x, word y) +static word big__sub(word x, word y) { word d = digit0(x) - digit0(y); word borrow = (d & IBASE) != 0; @@ -484,7 +513,7 @@ word bigtimes(word x, word y) word s = big_is_negative(y); for (word n = 0, d = digit0(y); y; n++, d = digit(y)) { if (d) { - r = bigplus(r, shift(n, stimes(x, d))); + r = bigplus(r, big__shift(n, big__stimes(x, d))); } y = rest(y); @@ -492,38 +521,6 @@ word bigtimes(word x, word y) return (s != big_is_negative(x) ? bignegate(r) : r); } -/* multiply big x by n'th power of IBASE */ -word shift(word n, word x) -{ - while (n--) { - x = make(INT, 0, x); - } - - return x; -} - -/* multiply big x (>=0) by digit n (>0) */ -word stimes(word x, word n) -{ - unsigned d = n * digit0(x); /* ignore sign of x */ - word carry = d >> DIGITWIDTH; - word r = make(INT, d & MAXDIGIT, 0); - word *y = &rest(r); - - while ((x = rest(x)) != 0) { - d = n * digit(x) + carry; - *y = make(INT, d & MAXDIGIT, 0); - y = &rest(*y); - carry = d >> DIGITWIDTH; - } - - if (carry) { - *y = make(INT, carry, 0); - } - - return r; -} - /* may assume y~=0 */ word big_divide(word x, word y) { |