diff options
| -rw-r--r-- | Include/longintrepr.h | 69 | ||||
| -rw-r--r-- | Include/longobject.h | 32 | ||||
| -rw-r--r-- | Objects/longobject.c | 900 |
3 files changed, 1001 insertions, 0 deletions
diff --git a/Include/longintrepr.h b/Include/longintrepr.h new file mode 100644 index 0000000..4184f8a --- /dev/null +++ b/Include/longintrepr.h @@ -0,0 +1,69 @@ +/*********************************************************** +Copyright 1991 by Stichting Mathematisch Centrum, Amsterdam, The +Netherlands. + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, +provided that the above copyright notice appear in all copies and that +both that copyright notice and this permission notice appear in +supporting documentation, and that the names of Stichting Mathematisch +Centrum or CWI not be used in advertising or publicity pertaining to +distribution of the software without specific, written prior permission. + +STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO +THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE +FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT +OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +******************************************************************/ + +/* Parameters of the long integer representation. + These shouldn't have to be changed as C should guarantee that a short + contains at least 16 bits, but it's made changeable any way. + Note: 'digit' should be able to hold 2*MASK+1, and 'twodigits' + should be able to hold the intermediate results in 'mul' + (at most MASK << SHIFT). + Also, x_sub assumes that 'digit' is an unsigned type, and overflow + is handled by taking the result mod 2**N for some N > SHIFT. + And, at some places it is assumed that MASK fits in an int, as well. */ + +typedef unsigned short digit; +typedef unsigned long twodigits; + +#define SHIFT 15 +#define BASE ((digit)1 << SHIFT) +#define MASK ((int)(BASE - 1)) + +/* Long integer representation. + The absolute value of a number is equal to + SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i) + Negative numbers are represented with ob_size < 0; + zero is represented by ob_size == 0. + In a normalized number, ob_digit[abs(ob_size)-1] (the most significant + digit) is never zero. Also, in all cases, for all valid i, + 0 <= ob_digit[i] <= MASK. + The allocation fuction takes care of allocating extra memory + so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually available. */ + +typedef struct { + OB_HEAD + int ob_size; /* XXX Hack! newvarobj() stores it as unsigned! */ + digit ob_digit[1]; +} longobject; + +#define ABS(x) ((x) < 0 ? -(x) : (x)) + +/* Internal use only */ +longobject *alloclongobject PROTO((int)); +longobject *long_normalize PROTO((longobject *)); +longobject *mul1 PROTO((longobject *, digit)); +longobject *muladd1 PROTO((longobject *, digit, digit)); +longobject *divrem1 PROTO((longobject *, digit, digit *)); + +/* Check for interrupts during operations on long ints >= this size */ +#define INTRLIMIT 20 diff --git a/Include/longobject.h b/Include/longobject.h new file mode 100644 index 0000000..862364d --- /dev/null +++ b/Include/longobject.h @@ -0,0 +1,32 @@ +/*********************************************************** +Copyright 1991 by Stichting Mathematisch Centrum, Amsterdam, The +Netherlands. + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, +provided that the above copyright notice appear in all copies and that +both that copyright notice and this permission notice appear in +supporting documentation, and that the names of Stichting Mathematisch +Centrum or CWI not be used in advertising or publicity pertaining to +distribution of the software without specific, written prior permission. + +STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO +THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE +FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT +OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +******************************************************************/ + +/* Long (arbitrary precision) integer object interface */ + +extern typeobject Longtype; + +#define is_longobject(op) ((op)->ob_type == &Longtype) + +extern object *newlongobject PROTO((long)); +extern long getlongvalue PROTO((object *)); diff --git a/Objects/longobject.c b/Objects/longobject.c new file mode 100644 index 0000000..e155608 --- /dev/null +++ b/Objects/longobject.c @@ -0,0 +1,900 @@ +/*********************************************************** +Copyright 1991 by Stichting Mathematisch Centrum, Amsterdam, The +Netherlands. + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, +provided that the above copyright notice appear in all copies and that +both that copyright notice and this permission notice appear in +supporting documentation, and that the names of Stichting Mathematisch +Centrum or CWI not be used in advertising or publicity pertaining to +distribution of the software without specific, written prior permission. + +STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO +THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE +FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT +OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +******************************************************************/ + +/* Long (arbitrary precision) integer object implementation */ + +#include "allobjects.h" +#include "longintrepr.h" +#include <assert.h> + +/* Normalize (remove leading zeros from) a long int object. + Doesn't attempt to free the storage--in most cases, due to the nature + of the algorithms used, this could save at most be one word anyway. */ + +longobject * +long_normalize(v) + register longobject *v; +{ + int j = ABS(v->ob_size); + register int i = j; + + while (i > 0 && v->ob_digit[i-1] == 0) + --i; + if (i != j) + v->ob_size = (v->ob_size < 0) ? -i : i; + return v; +} + +/* Allocate a new long int object with size digits. + Return NULL and set exception if we run out of memory. */ + +longobject * +alloclongobject(size) + int size; +{ + return NEWVAROBJ(longobject, &Longtype, size); +} + +/* Create a new long int object from a C long int */ + +object * +newlongobject(ival) + long ival; +{ + /* Assume a C long fits in at most 3 'digits' */ + longobject *v = alloclongobject(3); + if (v != NULL) { + if (ival < 0) { + ival = -ival; + v->ob_size = -v->ob_size; + } + v->ob_digit[0] = ival & MASK; + v->ob_digit[1] = (ival >> SHIFT) & MASK; + v->ob_digit[2] = (ival >> (2*SHIFT)) & MASK; + v = long_normalize(v); + } + return (object *)v; +} + +/* Get a C long int from a long int object. + Returns -1 and sets an error condition if overflow occurs. */ + +long +getlongvalue(vv) + object *vv; +{ + register longobject *v; + long x, prev; + int i, sign; + + if (vv == NULL || !is_longobject(vv)) { + err_badcall(); + return -1; + } + v = (longobject *)vv; + i = v->ob_size; + sign = 1; + x = 0; + if (i < 0) { + sign = -1; + i = -i; + } + while (--i >= 0) { + prev = x; + x = (x << SHIFT) + v->ob_digit[i]; + if ((x >> SHIFT) != prev) { + err_setstr(RuntimeError, + "long int too long to convert"); + return -1; + } + } + return x * sign; +} + +/* Get a C double from a long int object. No overflow check. */ + +double +dgetlongvalue(vv) + object *vv; +{ + register longobject *v; + double x; + double multiplier = (double) (1L << SHIFT); + int i, sign; + + if (vv == NULL || !is_longobject(vv)) { + err_badcall(); + return -1; + } + v = (longobject *)vv; + i = v->ob_size; + sign = 1; + x = 0.0; + if (i < 0) { + sign = -1; + i = -i; + } + while (--i >= 0) { + x = x*multiplier + v->ob_digit[i]; + } + return x * sign; +} + +/* Multiply by a single digit, ignoring the sign. */ + +longobject * +mul1(a, n) + longobject *a; + digit n; +{ + return muladd1(a, n, (digit)0); +} + +/* Multiply by a single digit and add a single digit, ignoring the sign. */ + +longobject * +muladd1(a, n, extra) + longobject *a; + digit n; + digit extra; +{ + int size_a = ABS(a->ob_size); + longobject *z = alloclongobject(size_a+1); + twodigits carry = extra; + int i; + + if (z == NULL) + return NULL; + for (i = 0; i < size_a; ++i) { + carry += (twodigits)a->ob_digit[i] * n; + z->ob_digit[i] = carry & MASK; + carry >>= SHIFT; + } + z->ob_digit[i] = carry; + return long_normalize(z); +} + +/* Divide a long integer by a digit, returning both the quotient + (as function result) and the remainder (through *prem). + The sign of a is ignored; n should not be zero. */ + +longobject * +divrem1(a, n, prem) + longobject *a; + digit n; + digit *prem; +{ + int size = ABS(a->ob_size); + longobject *z; + int i; + twodigits rem = 0; + + assert(n > 0 && n <= MASK); + z = alloclongobject(size); + if (z == NULL) + return NULL; + for (i = size; --i >= 0; ) { + rem = (rem << SHIFT) + a->ob_digit[i]; + z->ob_digit[i] = rem/n; + rem %= n; + } + *prem = rem; + return long_normalize(z); +} + +/* Convert a long int object to a string, using a given conversion base. + Return a string object. */ + +stringobject * +long_format(a, base) + longobject *a; + int base; +{ + stringobject *str; + int i; + int size_a = ABS(a->ob_size); + char *p; + int bits; + char sign = '\0'; + + assert(base >= 2 && base <= 36); + + /* Compute a rough upper bound for the length of the string */ + i = base; + bits = 0; + while (i > 1) { + ++bits; + i >>= 1; + } + i = 1 + (size_a*SHIFT + bits-1) / bits; + str = (stringobject *) newsizedstringobject((char *)0, i); + if (str == NULL) + return NULL; + p = GETSTRINGVALUE(str) + i; + *p = '\0'; + if (a->ob_size < 0) + sign = '-'; + + INCREF(a); + do { + digit rem; + longobject *temp = divrem1(a, (digit)base, &rem); + if (temp == NULL) { + DECREF(a); + DECREF(str); + return NULL; + } + if (rem < 10) + rem += '0'; + else + rem += 'A'-10; + assert(p > GETSTRINGVALUE(str)); + *--p = rem; + DECREF(a); + a = temp; + if (a->ob_size >= INTRLIMIT && intrcheck()) { + DECREF(a); + DECREF(str); + err_set(KeyboardInterrupt); + return NULL; + } + } while (a->ob_size != 0); + DECREF(a); + if (sign) + *--p = sign; + if (p != GETSTRINGVALUE(str)) { + char *q = GETSTRINGVALUE(str); + assert(p > q); + do { + } while ((*q++ = *p++) != '\0'); + resizestring((object **)&str, (int) (q - GETSTRINGVALUE(str))); + } + return str; +} + +/* Convert a string to a long int object, in a given base. + Base zero implies a default depending on the number. */ + +object * +long_scan(str, base) + char *str; + int base; +{ + int sign = 1; + longobject *z; + + assert(base == 0 || base >= 2 && base <= 36); + if (*str == '+') + ++str; + else if (*str == '-') { + ++str; + sign = -1; + } + if (base == 0) { + if (str[0] != '0') + base = 10; + else if (str[1] == 'x' || str[1] == 'X') + base = 16; + else + base = 8; + } + if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) + str += 2; + z = alloclongobject(0); + for ( ; z != NULL; ++str) { + int k = -1; + longobject *temp; + + if (*str <= '9') + k = *str - '0'; + else if (*str >= 'a') + k = *str - 'a' + 10; + else if (*str >= 'A') + k = *str - 'A' + 10; + if (k < 0 || k >= base) + break; + temp = muladd1(z, (digit)base, (digit)k); + DECREF(z); + z = temp; + } + if (z != NULL) + z->ob_size *= sign; + return (object *) z; +} + +static longobject *x_divrem PROTO((longobject *, longobject *, longobject **)); + +/* Long division with remainder, top-level routine */ + +longobject * +long_divrem(a, b, prem) + longobject *a, *b; + longobject **prem; +{ + int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); + longobject *z; + + if (size_b == 0) { + if (prem != NULL) + *prem = NULL; + err_setstr(RuntimeError, "long division by zero"); + return NULL; + } + if (size_a < size_b || + size_a == size_b && a->ob_digit[size_a-1] < b->ob_digit[size_b-1]) { + /* |a| < |b|. */ + if (prem != NULL) { + INCREF(a); + *prem = a; + } + return alloclongobject(0); + } + if (size_b == 1) { + digit rem = 0; + z = divrem1(a, b->ob_digit[0], &rem); + if (prem != NULL) { + if (z == NULL) + *prem = NULL; + else + *prem = (longobject *) + newlongobject((long)rem); + } + } + else + z = x_divrem(a, b, prem); + /* Set the signs. + The quotient z has the sign of a*b; + the remainder r has the sign of a, + so a = b*z + r. */ + if (z != NULL) { + if ((a->ob_size < 0) != (b->ob_size < 0)) + z->ob_size = - z->ob_size; + if (prem != NULL && *prem != NULL && a->ob_size < 0) + (*prem)->ob_size = - (*prem)->ob_size; + } + return z; +} + +/* True unsigned long division with remainder */ + +static longobject * +x_divrem(v1, w1, prem) + longobject *v1, *w1; + longobject **prem; +{ + int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); + digit d = (twodigits)BASE / (w1->ob_digit[size_w-1] + 1); + longobject *v = mul1(v1, d); + longobject *w = mul1(w1, d); + longobject *a; + int j, k; + + if (v == NULL || w == NULL) { + XDECREF(v); + XDECREF(w); + if (prem != NULL) + *prem = NULL; + return NULL; + } + + assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ + assert(v->refcnt == 1); /* Since v will be used as accumulator! */ + assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ + + size_v = ABS(v->ob_size); + a = alloclongobject(size_v - size_w + 1); + + for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) { + digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; + twodigits q; + long carry = 0; /* Signed! long! */ + int i; + + if (size_v >= INTRLIMIT && intrcheck()) { + DECREF(a); + a = NULL; + err_set(KeyboardInterrupt); + break; + } + if (vj == w->ob_digit[size_w-1]) + q = MASK; + else + q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / + w->ob_digit[size_w-1]; + + while (w->ob_digit[size_w-2]*q > + (( + ((twodigits)vj << SHIFT) + + v->ob_digit[j-1] + - q*w->ob_digit[size_w-1] + ) << SHIFT) + + v->ob_digit[j-2]) + --q; + + for (i = 0; i < size_w && i+k < size_v; ++i) { + twodigits z = w->ob_digit[i] * q; + digit zz = z >> SHIFT; + carry += v->ob_digit[i+k] - z + ((twodigits)zz << SHIFT); + v->ob_digit[i+k] = carry & MASK; + carry = (carry >> SHIFT) - zz; + } + + if (i+k < size_v) { + carry += v->ob_digit[i+k]; + v->ob_digit[i+k] = 0; + } + + if (carry == 0) + a->ob_digit[k] = q; + else { + assert(carry == -1); + a->ob_digit[k] = q-1; + carry = 0; + for (i = 0; i < size_w && i+k < size_v; ++i) { + carry += v->ob_digit[i+k] + w->ob_digit[i]; + v->ob_digit[i+k] = carry & MASK; + carry >>= SHIFT; + } + } + } /* for j, k */ + + if (a != NULL) + a = long_normalize(a); + if (prem != 0) { + if (a == NULL) + *prem = NULL; + else + *prem = divrem1(v, d, &d); + /* Using d as a dummy to receive the - unused - remainder */ + } + DECREF(v); + DECREF(w); + return a; +} + +/* Methods */ + +static void +long_dealloc(v) + longobject *v; +{ + DEL(v); +} + +static void +long_print(v, fp, flags) + longobject *v; + FILE *fp; + int flags; +{ + stringobject *str = long_format(v, 10); + if (str == NULL) { + err_clear(); + fprintf(fp, "[err]"); + } + else { + fprintf(fp, "%sL", GETSTRINGVALUE(str)); + DECREF(str); + } +} + +static object * +long_repr(v) + longobject *v; +{ + stringobject *str = long_format(v, 10); + if (str != NULL) { + int len = getstringsize((object *)str); + resizestring((object **)&str, len + 1); + if (str != NULL) + GETSTRINGVALUE(str)[len] = 'L'; + } + return (object *)str; +} + +static int +long_compare(a, b) + longobject *a, *b; +{ + int sign; + + if (a->ob_size != b->ob_size) + sign = a->ob_size - b->ob_size; + else { + int i = ABS(a->ob_size); + while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) + ; + if (i < 0) + sign = 0; + else + sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; + } + return sign; +} + +/* Add the absolute values of two long integers. */ + +static longobject *x_add PROTO((longobject *, longobject *)); +static longobject * +x_add(a, b) + longobject *a, *b; +{ + int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); + longobject *z; + int i; + digit carry = 0; + + /* Ensure a is the larger of the two: */ + if (size_a < size_b) { + { longobject *temp = a; a = b; b = temp; } + { int size_temp = size_a; size_a = size_b; size_b = size_temp; } + } + z = alloclongobject(size_a+1); + if (z == NULL) + return NULL; + for (i = 0; i < size_b; ++i) { + carry += a->ob_digit[i] + b->ob_digit[i]; + z->ob_digit[i] = carry & MASK; + /* The following assumes unsigned shifts don't + propagate the sign bit. */ + carry >>= SHIFT; + } + for (; i < size_a; ++i) { + carry += a->ob_digit[i]; + z->ob_digit[i] = carry & MASK; + carry >>= SHIFT; + } + z->ob_digit[i] = carry; + return long_normalize(z); +} + +/* Subtract the absolute values of two integers. */ + +static longobject *x_sub PROTO((longobject *, longobject *)); +static longobject * +x_sub(a, b) + longobject *a, *b; +{ + int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); + longobject *z; + int i; + int sign = 1; + digit borrow = 0; + + /* Ensure a is the larger of the two: */ + if (size_a < size_b) { + sign = -1; + { longobject *temp = a; a = b; b = temp; } + { int size_temp = size_a; size_a = size_b; size_b = size_temp; } + } + else if (size_a == size_b) { + /* Find highest digit where a and b differ: */ + i = size_a; + while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) + ; + if (i < 0) + return alloclongobject(0); + if (a->ob_digit[i] < b->ob_digit[i]) { + sign = -1; + { longobject *temp = a; a = b; b = temp; } + } + size_a = size_b = i+1; + } + z = alloclongobject(size_a); + if (z == NULL) + return NULL; + for (i = 0; i < size_b; ++i) { + /* The following assumes unsigned arithmetic + works module 2**N for some N>SHIFT. */ + borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; + z->ob_digit[i] = borrow & MASK; + borrow >>= SHIFT; + borrow &= 1; /* Keep only one sign bit */ + } + for (; i < size_a; ++i) { + borrow = a->ob_digit[i] - borrow; + z->ob_digit[i] = borrow & MASK; + borrow >>= SHIFT; + } + assert(borrow == 0); + z->ob_size *= sign; + return long_normalize(z); +} + +static object * +long_add(a, w) + longobject *a; + object *w; +{ + longobject *b; + longobject *z; + + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + b = (longobject *)w; + + if (a->ob_size < 0) { + if (b->ob_size < 0) { + z = x_add(a, b); + if (z != NULL) + z->ob_size = -z->ob_size; + } + else + z = x_sub(b, a); + } + else { + if (b->ob_size < 0) + z = x_sub(a, b); + else + z = x_add(a, b); + } + return (object *)z; +} + +static object * +long_sub(a, w) + longobject *a; + object *w; +{ + longobject *b; + longobject *z; + + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + b = (longobject *)w; + + if (a->ob_size < 0) { + if (b->ob_size < 0) + z = x_sub(a, b); + else + z = x_add(a, b); + if (z != NULL) + z->ob_size = -z->ob_size; + } + else { + if (b->ob_size < 0) + z = x_add(a, b); + else + z = x_sub(a, b); + } + return (object *)z; +} + +static object * +long_mul(a, w) + longobject *a; + object *w; +{ + longobject *b; + int size_a; + int size_b; + longobject *z; + int i; + + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + b = (longobject *)w; + size_a = ABS(a->ob_size); + size_b = ABS(b->ob_size); + z = alloclongobject(size_a + size_b); + if (z == NULL) + return NULL; + for (i = 0; i < z->ob_size; ++i) + z->ob_digit[i] = 0; + for (i = 0; i < size_a; ++i) { + twodigits carry = 0; + twodigits f = a->ob_digit[i]; + int j; + + if (z->ob_size >= INTRLIMIT && intrcheck()) { + DECREF(z); + err_set(KeyboardInterrupt); + return NULL; + } + for (j = 0; j < size_b; ++j) { + carry += z->ob_digit[i+j] + b->ob_digit[j] * f; + z->ob_digit[i+j] = carry & MASK; + carry >>= SHIFT; + } + for (; carry != 0; ++j) { + assert(i+j < z->ob_size); + carry += z->ob_digit[i+j]; + z->ob_digit[i+j] = carry & MASK; + carry >>= SHIFT; + } + } + if (a->ob_size < 0) + z->ob_size = -z->ob_size; + if (b->ob_size < 0) + z->ob_size = -z->ob_size; + return (object *) long_normalize(z); +} + +static object * +long_div(v, w) + longobject *v; + register object *w; +{ + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + return (object *) long_divrem(v, (longobject *)w, (longobject **)0); +} + +static object * +long_rem(v, w) + longobject *v; + register object *w; +{ + longobject *div, *rem = NULL; + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + div = long_divrem(v, (longobject *)w, &rem); + if (div == NULL) { + XDECREF(rem); + rem = NULL; + } + else { + DECREF(div); + } + return (object *) rem; +} + +/* The expression a mod b has the value a - b*floor(a/b). + The divrem function gives the remainder after division of + |a| by |b|, with the sign of a. This is also expressed + as a - b*trunc(a/b), if trunc truncates towards zero. + Some examples: + a b a rem b a mod b + 13 10 3 3 + -13 10 -3 7 + 13 -10 3 -7 + -13 -10 -3 -3 + So, to get from rem to mod, we have to add b if a and b + have different signs. */ + +static object * +long_divmod(v, w) + longobject *v; + register object *w; +{ + object *z; + longobject *div, *rem; + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + div = long_divrem(v, (longobject *)w, &rem); + if (div == NULL) { + XDECREF(rem); + return NULL; + } + if ((v->ob_size < 0) != (((longobject *)w)->ob_size < 0)) { + longobject *temp = (longobject *) long_add(rem, w); + DECREF(rem); + rem = temp; /* XXX ??? was rem = b ??? */ + if (rem == NULL) { + DECREF(div); + return NULL; + } + } + z = newtupleobject(2); + if (z != NULL) { + settupleitem(z, 0, (object *) div); + settupleitem(z, 1, (object *) rem); + } + else { + DECREF(div); + DECREF(rem); + } + return z; +} + +static object * +long_pow(v, w) + longobject *v; + register object *w; +{ + if (!is_longobject(w)) { + err_badarg(); + return NULL; + } + err_setstr(SystemError, "long power not implemented"); + return NULL; +} + +static object * +long_pos(v) + longobject *v; +{ + INCREF(v); + return (object *)v; +} + +static object * +long_neg(v) + longobject *v; +{ + longobject *z; + int i = v->ob_size; + if (i == 0) + return long_pos(v); + i = ABS(i); + z = alloclongobject(i); + if (z != NULL) { + z->ob_size = - v->ob_size; + while (--i >= 0) + z->ob_digit[i] = v->ob_digit[i]; + } + return (object *)z; +} + +static object * +long_abs(v) + longobject *v; +{ + if (v->ob_size < 0) + return long_neg(v); + else + return long_pos(v); +} + +static number_methods long_as_number = { + long_add, /*nb_add*/ + long_sub, /*nb_subtract*/ + long_mul, /*nb_multiply*/ + long_div, /*nb_divide*/ + long_rem, /*nb_remainder*/ + long_divmod, /*nb_divmod*/ + long_pow, /*nb_power*/ + long_neg, /*nb_negative*/ + long_pos, /*tp_positive*/ + long_abs, /*tp_absolute*/ +}; + +typeobject Longtype = { + OB_HEAD_INIT(&Typetype) + 0, + "long int", + sizeof(longobject) - sizeof(digit), + sizeof(digit), + long_dealloc, /*tp_dealloc*/ + long_print, /*tp_print*/ + 0, /*tp_getattr*/ + 0, /*tp_setattr*/ + long_compare, /*tp_compare*/ + long_repr, /*tp_repr*/ + &long_as_number,/*tp_as_number*/ + 0, /*tp_as_sequence*/ + 0, /*tp_as_mapping*/ +}; |