[bigint/bigint.git] / BigInteger.cc

/*
* Matt McCutchen's Big Integer Library
* http://mysite.verizon.net/mccutchen/bigint/
*/

#include "BigInteger.hh"

// MANAGEMENT

// Assignment operator
void BigInteger::operator =(const BigInteger &x) {
	// Calls like a = a have no effect
	if (this == &x)
		return;
	// Copy sign
	sign = x.sign;
	// Copy the rest
	BigUnsigned::operator =(x);
}

// Constructor from an array of blocks and a sign
BigInteger::BigInteger(const Blk *b, Index l, Sign s) : BigUnsigned(b, l) {
	switch (s) {
		case zero:
		case positive:
		case negative:
		sign = (len == 0) ? zero : s;
		break;
		default:
		throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
	}
}

// Constructor from a BigUnsigned and a sign
BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) {
	switch (s) {
		case zero:
		case positive:
		case negative:
		sign = (len == 0) ? zero : s;
		break;
		default:
		throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
	}
}

/*
* The steps for construction of a BigInteger
* from an integral value x are as follows:
* 1. If x is zero, create an empty BigInteger and stop.
* 2. Allocate a one-block number array.
* 3. If x is positive (or of an unsigned type), set the
*    sign of the BigInteger to positive.
* 4. If x is of a signed type and is negative, set the
*    sign of the BigInteger to negative.
* 5. If x is of a signed type, convert x (or -x if x < 0)
*    to the unsigned type of the same length.
* 6. Expand x (or the result of step 5) to a Blk,
*    and store it in the number array.
*/

BigInteger::BigInteger(unsigned long x) {
	if (x == 0) {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	} else {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	}
}

BigInteger::BigInteger(long x) {
	if (x > 0) {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	} else if (x < 0) {
		cap = 1;
		blk = new Blk[1];
		sign = negative;
		len = 1;
		*blk = Blk(-x);
	} else {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	}
}

BigInteger::BigInteger(unsigned int x) {
	if (x == 0) {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	} else {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	}
}

BigInteger::BigInteger(int x) {
	if (x > 0) {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	} else if (x < 0) {
		cap = 1;
		blk = new Blk[1];
		sign = negative;
		len = 1;
		*blk = Blk(-x);
	} else {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	}
}

BigInteger::BigInteger(unsigned short x) {
	if (x == 0) {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	} else {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	}
}

BigInteger::BigInteger(short x) {
	if (x > 0) {
		cap = 1;
		blk = new Blk[1];
		sign = positive;
		len = 1;
		*blk = Blk(x);
	} else if (x < 0) {
		cap = 1;
		blk = new Blk[1];
		sign = negative;
		len = 1;
		*blk = Blk(-x);
	} else {
		cap = 0;
		blk = new Blk[0];
		sign = zero;
		len = 0;
	}
}

// CONVERTERS
/*
* The steps for conversion of a BigInteger to an
* integral type are as follows:
* 1. If the BigInteger is zero, return zero.
* 2. If the BigInteger is positive:
*    3. If it is more than one block long or its lowest
*       block has bits set out of the range of the target
*       type, throw an exception.
*    4. Otherwise, convert the lowest block to the
*       target type and return it.
* 5. If the BigInteger is negative:
*    6. If the target type is unsigned, throw an exception.
*    7. If it is more than one block long or its lowest
*       block has bits set out of the range of the target
*       type, throw an exception.
*    8. Otherwise, convert the lowest block to the
*       target type, negate it, and return it.
*/

namespace {
	// These masks are used to test whether a Blk has bits
	// set out of the range of a smaller integral type.  Note
	// that this range is not considered to include the sign bit.
	const BigUnsigned::Blk  lMask = ~0 >> 1;
	const BigUnsigned::Blk uiMask = (unsigned int)(~0);
	const BigUnsigned::Blk  iMask = uiMask >> 1;
	const BigUnsigned::Blk usMask = (unsigned short)(~0);
	const BigUnsigned::Blk  sMask = usMask >> 1;
}

BigInteger::operator unsigned long() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1)
			return *blk;
		else
			throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long";
		case negative:
		throw "BigInteger operator unsigned long() const: Cannot convert a negative integer to an unsigned type";
		default:
		throw "BigInteger: Internal error";
	}
}

BigInteger::operator long() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1 && (*blk & ~lMask) == 0)
			return long(*blk);
		else
			throw "BigInteger operator long() const: Value is too big for a long";
		case negative:
		if (len == 1 && (*blk & ~lMask) == 0)
			return -long(*blk);
		else
			throw "BigInteger operator long() const: Value is too big for a long";
		default:
		throw "BigInteger: Internal error";
	}
}

BigInteger::operator unsigned int() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1 && (*blk & ~uiMask) == 0)
			return (unsigned int)(*blk);
		else
			throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int";
		case negative:
		throw "BigInteger operator unsigned int() const: Cannot convert a negative integer to an unsigned type";
		default:
		throw "BigInteger: Internal error";
	}
}

BigInteger::operator int() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1 && (*blk & ~iMask) == 0)
			return int(*blk);
		else
			throw "BigInteger operator int() const: Value is too big for an int";
		case negative:
		if (len == 1 && (*blk & ~iMask) == 0)
			return -int(*blk);
		else
			throw "BigInteger operator int() const: Value is too big for an int";
		default:
		throw "BigInteger: Internal error";
	}
}

BigInteger::operator unsigned short() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1 && (*blk & ~usMask) == 0)
			return (unsigned short)(*blk);
		else
			throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short";
		case negative:
		throw "BigInteger operator unsigned short() const: Cannot convert a negative integer to an unsigned type";
		default:
		throw "BigInteger: Internal error";
	}
}

BigInteger::operator short() const {
	switch (sign) {
		case zero:
		return 0;
		case positive:
		if (len == 1 && (*blk & ~sMask) == 0)
			return short(*blk);
		else
			throw "BigInteger operator short() const: Value is too big for a short";
		case negative:
		if (len == 1 && (*blk & ~sMask) == 0)
			return -short(*blk);
		else
			throw "BigInteger operator short() const: Value is too big for a short";
		default:
		throw "BigInteger: Internal error";
	}
}

// COMPARISON
BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
	// A greater sign implies a greater number
	if (sign < x.sign)
		return less;
	else if (sign > x.sign)
		return greater;
	else switch (sign) {
		// If the signs are the same...
		case zero:
		return equal; // Two zeros are equal
		case positive:
		// Compare the magnitudes
		return BigUnsigned::compareTo(x);
		case negative:
		// Compare the magnitudes, but return the opposite result
		return CmpRes(-BigUnsigned::compareTo(x));
		default:
		throw "BigInteger: Internal error";
	}
}

// PUT-HERE OPERATIONS
// These do some messing around to determine the sign of the result,
// then call one of BigUnsigned's put-heres.

// Addition
void BigInteger::add(const BigInteger &a, const BigInteger &b) {
	// Block unsafe calls
	if (this == &a || this == &b)
		throw "BigInteger::add: One of the arguments is the invoked object";
	// If one argument is zero, copy the other.
	if (a.sign == zero)
		operator =(b);
	else if (b.sign == zero)
		operator =(a);
	// If the arguments have the same sign, take the
	// common sign and add their magnitudes.
	else if (a.sign == b.sign) {
		sign = a.sign;
		BigUnsigned::add(a, b);
	} else {
		// Otherwise, their magnitudes must be compared.
		switch (a.BigUnsigned::compareTo(b)) {
			// If their magnitudes are the same, copy zero.
			case equal:
			len = 0;
			sign = zero;
			break;
			// Otherwise, take the sign of the greater, and subtract
			// the lesser magnitude from the greater magnitude.
			case greater:
			sign = a.sign;
			BigUnsigned::subtract(a, b);
			break;
			case less:
			sign = b.sign;
			BigUnsigned::subtract(b, a);
			break;
		}
	}
}

// Subtraction
void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
	// Notice that this routine is identical to BigInteger::add,
	// if one replaces b.sign by its opposite.
	// Block unsafe calls
	if (this == &a || this == &b)
		throw "BigInteger::subtract: One of the arguments is the invoked object";
	// If a is zero, copy b and flip its sign.  If b is zero, copy a.
	if (a.sign == zero) {
		BigUnsigned::operator =(b);
		sign = Sign(-sign);
	} else if (b.sign == zero)
    operator =(a);
	// If their signs differ, take a.sign and add the magnitudes.
	else if (a.sign != b.sign) {
		sign = a.sign;
		BigUnsigned::add(a, b);
	} else {
		// Otherwise, their magnitudes must be compared.
		switch (a.BigUnsigned::compareTo(b)) {
			// If their magnitudes are the same, copy zero.
			case equal:
			len = 0;
			sign = zero;
			break;
			// If a's magnitude is greater, take a.sign and
			// subtract a from b.
			case greater:
			sign = a.sign;
			BigUnsigned::subtract(a, b);
			break;
			// If b's magnitude is greater, take the opposite
			// of b.sign and subtract b from a.
			case less:
			sign = Sign(-b.sign);
			BigUnsigned::subtract(b, a);
			break;
		}
	}
}

// Multiplication
void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
	// Block unsafe calls
	if (this == &a || this == &b)
		throw "BigInteger::multiply: One of the arguments is the invoked object";
	// If one object is zero, copy zero and return.
	if (a.sign == zero || b.sign == zero) {
		sign = zero;
		len = 0;
		return;
	}
	// If the signs of the arguments are the same, the result
	// is positive, otherwise it is negative.
	sign = (a.sign == b.sign) ? positive : negative;
	// Multiply the magnitudes.
	BigUnsigned::multiply(a, b);
}

/*
* DIVISION WITH REMAINDER
* Please read the comments before the definition of
* `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
* information you should know before reading this function.
*
* Following Knuth, I decree that x / y is to be
* 0 if y==0 and floor(real-number x / y) if y!=0.
* Then x % y shall be x - y*(integer x / y).
*
* Note that x = y * (x / y) + (x % y) always holds.
* In addition, (x % y) is from 0 to y - 1 if y > 0,
* and from -(|y| - 1) to 0 if y < 0.  (x % y) = x if y = 0.
*
* Examples: (q = a / b, r = a % b)
*	a	b	q	r
*	===	===	===	===
*	4	3	1	1
*	-4	3	-2	2
*	4	-3	-2	-2
*	-4	-3	1	-1
*/
void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
	// Block unsafe calls
	if (this == &b || this == &q || &b == &q)
		throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object";
	// Division by zero gives quotient 0 and remainder *this
	if (b.sign == zero) {
		q.len = 0;
		q.sign = zero;
		return;
	}
	// 0 / b gives quotient 0 and remainder 0
	if (sign == zero) {
		q.len = 0;
		q.sign = zero;
		return;
	}
	
	// Here *this != 0, b != 0.
	
	// Do the operands have the same sign?
	if (sign == b.sign) {
		// Yes: easy case.  Quotient is zero or positive.
		q.sign = positive;
	} else {
		// No: harder case.  Quotient is negative.
		q.sign = negative;
		// Decrease the magnitude of the dividend by one.
		BigUnsigned::operator --();
		/*
		* We tinker with the dividend before and with the
		* quotient and remainder after so that the result
		* comes out right.  To see why it works, consider the following
		* list of examples, where A is the magnitude-decreased
		* a, Q and R are the results of BigUnsigned division
		* with remainder on A and |b|, and q and r are the
		* final results we want:
		*
		*	a	A	b	Q	R	q	r
		*	-3	-2	3	0	2	-1	0
		*	-4	-3	3	1	0	-2	2
		*	-5	-4	3	1	1	-2	1
		*	-6	-5	3	1	2	-2	0
		*
		* It appears that we need a total of 3 corrections:
		* Decrease the magnitude of a to get A.  Increase the
		* magnitude of Q to get q (and make it negative).
		* Find r = (b - 1) - R and give it the desired sign.
		*/
	}
	
	// Divide the magnitudes.
	BigUnsigned::divideWithRemainder(b, q);
	
	if (sign != b.sign) {
		// More for the harder case (as described):
		// Increase the magnitude of the quotient by one.
		q.BigUnsigned::operator ++();
		// Modify the remainder.
		BigUnsigned temp(*this);
		BigUnsigned::subtract(b, temp);
		BigUnsigned::operator --();
	}
	
	// Sign of the remainder is always the sign of the divisor b.
	sign = b.sign;
	
	// Set signs to zero as necessary.  (Thanks David Allen!)
	if (len == 0)
		sign = zero;
	if (q.len == 0)
		q.sign = zero;
	
	// WHEW!!!
}

// Negation
void BigInteger::negate(const BigInteger &a) {
	// Block unsafe calls
	if (this == &a)
		throw "BigInteger::negate: The argument is the invoked object";
	// Copy a's magnitude
	BigUnsigned::operator =(a);
	// Copy the opposite of a.sign
	sign = Sign(-a.sign);
}

// INCREMENT/DECREMENT OPERATORS

// Prefix increment
void BigInteger::operator ++() {
	switch (sign) {
		case zero:
		allocate(1);
		sign = positive;
		len = 1;
		*blk = 1;
		break;
		case positive:
		BigUnsigned::operator ++();
		break;
		case negative:
		BigUnsigned::operator --();
		if (len == 0)
			sign = zero;
		break;
	}
}

// Postfix increment: same as prefix
void BigInteger::operator ++(int) {
	operator ++();
}

// Prefix decrement
void BigInteger::operator --() {
	switch (sign) {
		case zero:
		allocate(1);
		sign = negative;
		len = 1;
		*blk = 1;
		break;
		case negative:
		BigUnsigned::operator ++();
		break;
		case positive:
		BigUnsigned::operator --();
		if (len == 0)
			sign = zero;
		break;
	}
}

// Postfix decrement: same as prefix
void BigInteger::operator --(int) {
	operator --();
}
Commit	Line	Data
e67d6049 MM	1	/*
e67d6049 MM	2	* Matt McCutchen's Big Integer Library
05780f4b	3	* http://mysite.verizon.net/mccutchen/bigint/
e67d6049 MM	4	*/
e67d6049 MM	5
05780f4b	6	#include "BigInteger.hh"
e67d6049 MM	7
	8	// MANAGEMENT
	9
	10	// Assignment operator
	11	void BigInteger::operator =(const BigInteger &x) {
	12	// Calls like a = a have no effect
	13	if (this == &x)
	14	return;
	15	// Copy sign
	16	sign = x.sign;
	17	// Copy the rest
	18	BigUnsigned::operator =(x);
	19	}
	20
	21	// Constructor from an array of blocks and a sign
05780f4b	22	BigInteger::BigInteger(const Blk *b, Index l, Sign s) : BigUnsigned(b, l) {
e67d6049 MM	23	switch (s) {
	24	case zero:
	25	case positive:
	26	case negative:
	27	sign = (len == 0) ? zero : s;
	28	break;
	29	default:
05780f4b	30	throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
e67d6049 MM	31	}
	32	}
	33
	34	// Constructor from a BigUnsigned and a sign
	35	BigInteger::BigInteger(const BigUnsigned &x, Sign s) : BigUnsigned(x) {
	36	switch (s) {
	37	case zero:
	38	case positive:
	39	case negative:
	40	sign = (len == 0) ? zero : s;
	41	break;
	42	default:
05780f4b	43	throw "BigInteger::BigInteger(Blk *, Index, Sign): Invalid sign";
e67d6049 MM	44	}
	45	}
	46
	47	/*
	48	* The steps for construction of a BigInteger
	49	* from an integral value x are as follows:
	50	* 1. If x is zero, create an empty BigInteger and stop.
	51	* 2. Allocate a one-block number array.
	52	* 3. If x is positive (or of an unsigned type), set the
	53	* sign of the BigInteger to positive.
	54	* 4. If x is of a signed type and is negative, set the
	55	* sign of the BigInteger to negative.
	56	* 5. If x is of a signed type, convert x (or -x if x < 0)
	57	* to the unsigned type of the same length.
	58	* 6. Expand x (or the result of step 5) to a Blk,
	59	* and store it in the number array.
	60	*/
	61
	62	BigInteger::BigInteger(unsigned long x) {
	63	if (x == 0) {
	64	cap = 0;
	65	blk = new Blk[0];
	66	sign = zero;
	67	len = 0;
	68	} else {
	69	cap = 1;
	70	blk = new Blk[1];
	71	sign = positive;
	72	len = 1;
	73	*blk = Blk(x);
	74	}
	75	}
	76
	77	BigInteger::BigInteger(long x) {
	78	if (x > 0) {
	79	cap = 1;
	80	blk = new Blk[1];
	81	sign = positive;
	82	len = 1;
	83	*blk = Blk(x);
	84	} else if (x < 0) {
	85	cap = 1;
	86	blk = new Blk[1];
	87	sign = negative;
	88	len = 1;
	89	*blk = Blk(-x);
	90	} else {
	91	cap = 0;
	92	blk = new Blk[0];
	93	sign = zero;
	94	len = 0;
	95	}
	96	}
	97
	98	BigInteger::BigInteger(unsigned int x) {
	99	if (x == 0) {
	100	cap = 0;
	101	blk = new Blk[0];
	102	sign = zero;
	103	len = 0;
	104	} else {
	105	cap = 1;
	106	blk = new Blk[1];
	107	sign = positive;
108	len = 1;
109	*blk = Blk(x);
110	}
111	}
112
113	BigInteger::BigInteger(int x) {
114	if (x > 0) {
115	cap = 1;
116	blk = new Blk[1];
117	sign = positive;
118	len = 1;
119	*blk = Blk(x);
120	} else if (x < 0) {
121	cap = 1;
122	blk = new Blk[1];
123	sign = negative;
124	len = 1;
125	*blk = Blk(-x);
126	} else {
127	cap = 0;
128	blk = new Blk[0];
129	sign = zero;
130	len = 0;
131	}
132	}
133
134	BigInteger::BigInteger(unsigned short x) {
135	if (x == 0) {
136	cap = 0;
137	blk = new Blk[0];
138	sign = zero;
139	len = 0;
140	} else {
141	cap = 1;
142	blk = new Blk[1];
143	sign = positive;
144	len = 1;
145	*blk = Blk(x);
146	}
147	}
148
149	BigInteger::BigInteger(short x) {
150	if (x > 0) {
151	cap = 1;
152	blk = new Blk[1];
153	sign = positive;
154	len = 1;
155	*blk = Blk(x);
156	} else if (x < 0) {
157	cap = 1;
158	blk = new Blk[1];
159	sign = negative;
160	len = 1;
161	*blk = Blk(-x);
162	} else {
163	cap = 0;
164	blk = new Blk[0];
165	sign = zero;
166	len = 0;
167	}
168	}
169
170	// CONVERTERS
171	/*
172	* The steps for conversion of a BigInteger to an
173	* integral type are as follows:
174	* 1. If the BigInteger is zero, return zero.
175	* 2. If the BigInteger is positive:
176	* 3. If it is more than one block long or its lowest
177	* block has bits set out of the range of the target
178	* type, throw an exception.
179	* 4. Otherwise, convert the lowest block to the
180	* target type and return it.
181	* 5. If the BigInteger is negative:
182	* 6. If the target type is unsigned, throw an exception.
183	* 7. If it is more than one block long or its lowest
184	* block has bits set out of the range of the target
185	* type, throw an exception.
186	* 8. Otherwise, convert the lowest block to the
187	* target type, negate it, and return it.
188	*/
189
190	namespace {
191	// These masks are used to test whether a Blk has bits
192	// set out of the range of a smaller integral type. Note
193	// that this range is not considered to include the sign bit.
194	const BigUnsigned::Blk lMask = ~0 >> 1;
195	const BigUnsigned::Blk uiMask = (unsigned int)(~0);
196	const BigUnsigned::Blk iMask = uiMask >> 1;
197	const BigUnsigned::Blk usMask = (unsigned short)(~0);
198	const BigUnsigned::Blk sMask = usMask >> 1;
199	}
200
201	BigInteger::operator unsigned long() const {
202	switch (sign) {
203	case zero:
204	return 0;
205	case positive:
206	if (len == 1)
207	return *blk;
208	else
209	throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long";
210	case negative:
211	throw "BigInteger operator unsigned long() const: Cannot convert a negative integer to an unsigned type";
212	default:
213	throw "BigInteger: Internal error";
214	}
215	}
216
217	BigInteger::operator long() const {
218	switch (sign) {
219	case zero:
220	return 0;
221	case positive:
222	if (len == 1 && (*blk & ~lMask) == 0)
223	return long(*blk);
224	else
225	throw "BigInteger operator long() const: Value is too big for a long";
226	case negative:
227	if (len == 1 && (*blk & ~lMask) == 0)
228	return -long(*blk);
229	else
230	throw "BigInteger operator long() const: Value is too big for a long";
231	default:
232	throw "BigInteger: Internal error";
233	}
234	}
235
236	BigInteger::operator unsigned int() const {
237	switch (sign) {
238	case zero:
239	return 0;
240	case positive:
241	if (len == 1 && (*blk & ~uiMask) == 0)
242	return (unsigned int)(*blk);
243	else
244	throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int";
245	case negative:
246	throw "BigInteger operator unsigned int() const: Cannot convert a negative integer to an unsigned type";
247	default:
248	throw "BigInteger: Internal error";
249	}
250	}
251
252	BigInteger::operator int() const {
253	switch (sign) {
254	case zero:
255	return 0;
256	case positive:
257	if (len == 1 && (*blk & ~iMask) == 0)
258	return int(*blk);
259	else
260	throw "BigInteger operator int() const: Value is too big for an int";
261	case negative:
262	if (len == 1 && (*blk & ~iMask) == 0)
263	return -int(*blk);
264	else
265	throw "BigInteger operator int() const: Value is too big for an int";
266	default:
267	throw "BigInteger: Internal error";
268	}
269	}
270
271	BigInteger::operator unsigned short() const {
272	switch (sign) {
273	case zero:
274	return 0;
275	case positive:
276	if (len == 1 && (*blk & ~usMask) == 0)
277	return (unsigned short)(*blk);
278	else
279	throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short";
280	case negative:
281	throw "BigInteger operator unsigned short() const: Cannot convert a negative integer to an unsigned type";
282	default:
283	throw "BigInteger: Internal error";
284	}
285	}
286
287	BigInteger::operator short() const {
288	switch (sign) {
289	case zero:
290	return 0;
291	case positive:
292	if (len == 1 && (*blk & ~sMask) == 0)
293	return short(*blk);
294	else
295	throw "BigInteger operator short() const: Value is too big for a short";
296	case negative:
297	if (len == 1 && (*blk & ~sMask) == 0)
298	return -short(*blk);
299	else
300	throw "BigInteger operator short() const: Value is too big for a short";
301	default:
302	throw "BigInteger: Internal error";
303	}
304	}
305
306	// COMPARISON
307	BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
308	// A greater sign implies a greater number
309	if (sign < x.sign)
310	return less;
311	else if (sign > x.sign)
312	return greater;
313	else switch (sign) {
314	// If the signs are the same...
315	case zero:
316	return equal; // Two zeros are equal
317	case positive:
318	// Compare the magnitudes
319	return BigUnsigned::compareTo(x);
320	case negative:
321	// Compare the magnitudes, but return the opposite result
322	return CmpRes(-BigUnsigned::compareTo(x));
323	default:
324	throw "BigInteger: Internal error";
325	}
326	}
327
328	// PUT-HERE OPERATIONS
329	// These do some messing around to determine the sign of the result,
330	// then call one of BigUnsigned's put-heres.
331
332	// Addition
333	void BigInteger::add(const BigInteger &a, const BigInteger &b) {
334	// Block unsafe calls
335	if (this == &a \|\| this == &b)
336	throw "BigInteger::add: One of the arguments is the invoked object";
337	// If one argument is zero, copy the other.
338	if (a.sign == zero)
339	operator =(b);
340	else if (b.sign == zero)
341	operator =(a);
342	// If the arguments have the same sign, take the
343	// common sign and add their magnitudes.
344	else if (a.sign == b.sign) {
345	sign = a.sign;
346	BigUnsigned::add(a, b);
347	} else {
348	// Otherwise, their magnitudes must be compared.
349	switch (a.BigUnsigned::compareTo(b)) {
350	// If their magnitudes are the same, copy zero.
351	case equal:
352	len = 0;
353	sign = zero;
354	break;
355	// Otherwise, take the sign of the greater, and subtract
356	// the lesser magnitude from the greater magnitude.
357	case greater:
358	sign = a.sign;
359	BigUnsigned::subtract(a, b);
360	break;
361	case less:
362	sign = b.sign;
363	BigUnsigned::subtract(b, a);
364	break;
365	}
366	}
367	}
368
369	// Subtraction
370	void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
371	// Notice that this routine is identical to BigInteger::add,
372	// if one replaces b.sign by its opposite.
373	// Block unsafe calls
374	if (this == &a \|\| this == &b)
375	throw "BigInteger::subtract: One of the arguments is the invoked object";
376	// If a is zero, copy b and flip its sign. If b is zero, copy a.
377	if (a.sign == zero) {
378	BigUnsigned::operator =(b);
379	sign = Sign(-sign);
380	} else if (b.sign == zero)
381	operator =(a);
382	// If their signs differ, take a.sign and add the magnitudes.
383	else if (a.sign != b.sign) {
384	sign = a.sign;
385	BigUnsigned::add(a, b);
386	} else {
387	// Otherwise, their magnitudes must be compared.
388	switch (a.BigUnsigned::compareTo(b)) {
389	// If their magnitudes are the same, copy zero.
390	case equal:
391	len = 0;
392	sign = zero;
393	break;
394	// If a's magnitude is greater, take a.sign and
395	// subtract a from b.
396	case greater:
397	sign = a.sign;
398	BigUnsigned::subtract(a, b);
399	break;
400	// If b's magnitude is greater, take the opposite
401	// of b.sign and subtract b from a.
402	case less:
403	sign = Sign(-b.sign);
404	BigUnsigned::subtract(b, a);
405	break;
406	}
407	}
408	}
409
410	// Multiplication
411	void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
412	// Block unsafe calls
413	if (this == &a \|\| this == &b)
414	throw "BigInteger::multiply: One of the arguments is the invoked object";
415	// If one object is zero, copy zero and return.
416	if (a.sign == zero \|\| b.sign == zero) {
417	sign = zero;
418	len = 0;
419	return;
420	}
421	// If the signs of the arguments are the same, the result
422	// is positive, otherwise it is negative.
423	sign = (a.sign == b.sign) ? positive : negative;
424	// Multiply the magnitudes.
425	BigUnsigned::multiply(a, b);
426	}
427
05780f4b MM	428	/*
	429	* DIVISION WITH REMAINDER
	430	* Please read the comments before the definition of
	431	* `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
	432	* information you should know before reading this function.
	433	*
	434	* Following Knuth, I decree that x / y is to be
	435	* 0 if y==0 and floor(real-number x / y) if y!=0.
	436	* Then x % y shall be x - y*(integer x / y).
	437	*
	438	* Note that x = y * (x / y) + (x % y) always holds.
	439	* In addition, (x % y) is from 0 to y - 1 if y > 0,
	440	* and from -(\|y\| - 1) to 0 if y < 0. (x % y) = x if y = 0.
	441	*
	442	* Examples: (q = a / b, r = a % b)
	443	* a b q r
	444	* === === === ===
	445	* 4 3 1 1
	446	* -4 3 -2 2
	447	* 4 -3 -2 -2
	448	* -4 -3 1 -1
	449	*/
	450	void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
e67d6049	451	// Block unsafe calls
05780f4b MM	452	if (this == &b \|\| this == &q \|\| &b == &q)
	453	throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object";
	454	// Division by zero gives quotient 0 and remainder *this
	455	if (b.sign == zero) {
	456	q.len = 0;
	457	q.sign = zero;
e67d6049 MM	458	return;
e67d6049 MM	459	}
05780f4b MM	460	// 0 / b gives quotient 0 and remainder 0
	461	if (sign == zero) {
	462	q.len = 0;
	463	q.sign = zero;
e67d6049 MM	464	return;
e67d6049 MM	465	}
05780f4b MM	466
	467	// Here *this != 0, b != 0.
	468
	469	// Do the operands have the same sign?
	470	if (sign == b.sign) {
	471	// Yes: easy case. Quotient is zero or positive.
	472	q.sign = positive;
	473	} else {
	474	// No: harder case. Quotient is negative.
	475	q.sign = negative;
	476	// Decrease the magnitude of the dividend by one.
	477	BigUnsigned::operator --();
	478	/*
	479	* We tinker with the dividend before and with the
	480	* quotient and remainder after so that the result
	481	* comes out right. To see why it works, consider the following
	482	* list of examples, where A is the magnitude-decreased
	483	* a, Q and R are the results of BigUnsigned division
	484	* with remainder on A and \|b\|, and q and r are the
	485	* final results we want:
	486	*
	487	* a A b Q R q r
	488	* -3 -2 3 0 2 -1 0
	489	* -4 -3 3 1 0 -2 2
	490	* -5 -4 3 1 1 -2 1
	491	* -6 -5 3 1 2 -2 0
	492	*
	493	* It appears that we need a total of 3 corrections:
	494	* Decrease the magnitude of a to get A. Increase the
	495	* magnitude of Q to get q (and make it negative).
	496	* Find r = (b - 1) - R and give it the desired sign.
	497	*/
	498	}
	499
	500	// Divide the magnitudes.
	501	BigUnsigned::divideWithRemainder(b, q);
	502
	503	if (sign != b.sign) {
	504	// More for the harder case (as described):
	505	// Increase the magnitude of the quotient by one.
	506	q.BigUnsigned::operator ++();
	507	// Modify the remainder.
	508	BigUnsigned temp(*this);
	509	BigUnsigned::subtract(b, temp);
	510	BigUnsigned::operator --();
	511	}
	512
	513	// Sign of the remainder is always the sign of the divisor b.
	514	sign = b.sign;
	515
	516	// Set signs to zero as necessary. (Thanks David Allen!)
e67d6049 MM	517	if (len == 0)
e67d6049 MM	518	sign = zero;
05780f4b MM	519	if (q.len == 0)
	520	q.sign = zero;
	521
	522	// WHEW!!!
e67d6049 MM	523	}
	524
	525	// Negation
	526	void BigInteger::negate(const BigInteger &a) {
	527	// Block unsafe calls
	528	if (this == &a)
	529	throw "BigInteger::negate: The argument is the invoked object";
	530	// Copy a's magnitude
	531	BigUnsigned::operator =(a);
	532	// Copy the opposite of a.sign
	533	sign = Sign(-a.sign);
	534	}
	535
	536	// INCREMENT/DECREMENT OPERATORS
	537
	538	// Prefix increment
	539	void BigInteger::operator ++() {
	540	switch (sign) {
	541	case zero:
	542	allocate(1);
	543	sign = positive;
	544	len = 1;
	545	*blk = 1;
	546	break;
	547	case positive:
	548	BigUnsigned::operator ++();
	549	break;
	550	case negative:
	551	BigUnsigned::operator --();
	552	if (len == 0)
	553	sign = zero;
	554	break;
	555	}
	556	}
	557
	558	// Postfix increment: same as prefix
	559	void BigInteger::operator ++(int) {
	560	operator ++();
	561	}
	562
	563	// Prefix decrement
	564	void BigInteger::operator --() {
	565	switch (sign) {
	566	case zero:
	567	allocate(1);
	568	sign = negative;
	569	len = 1;
	570	*blk = 1;
	571	break;
	572	case negative:
	573	BigUnsigned::operator ++();
	574	break;
	575	case positive:
	576	BigUnsigned::operator --();
	577	if (len == 0)
	578	sign = zero;
	579	break;
	580	}
	581	}
	582
	583	// Postfix decrement: same as prefix
	584	void BigInteger::operator --(int) {
	585	operator --();
	586	}
587