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