Commit | Line | Data |
---|---|---|
e67d6049 MM |
1 | /* |
2 | * Matt McCutchen's Big Integer Library | |
3 | * See: http://mysite.verizon.net/mccutchen/bigint/ | |
4 | */ | |
5 | ||
6 | #include "BigInteger.h" | |
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 | |
22 | BigInteger::BigInteger(const Blk *b, BlkNum l, Sign s) : BigUnsigned(b, l) { | |
23 | switch (s) { | |
24 | case zero: | |
25 | case positive: | |
26 | case negative: | |
27 | sign = (len == 0) ? zero : s; | |
28 | break; | |
29 | default: | |
30 | throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign"; | |
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: | |
43 | throw "BigInteger::BigInteger(Blk *, BlkNum, Sign): Invalid sign"; | |
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 | ||
428 | // Division | |
429 | void BigInteger::divide(const BigInteger &a, const BigInteger &b) { | |
430 | // Block unsafe calls | |
431 | if (this == &a || this == &b) | |
432 | throw "BigInteger::divide: One of the arguments is the invoked object"; | |
433 | // If b is zero, the caller has tried to divide by zero. Throw an exception. | |
434 | if (b.sign == zero) | |
435 | throw "BigInteger::divide: Division by zero"; | |
436 | // Otherwise if a is zero, copy zero and return. | |
437 | else if (a.sign == zero) { | |
438 | sign = zero; | |
439 | len = 0; | |
440 | return; | |
441 | } | |
442 | // If the signs of the arguments are the same, the result | |
443 | // is positive, otherwise it is negative. | |
444 | sign = (a.sign == b.sign) ? positive : negative; | |
445 | // Divide the magnitudes. | |
446 | // Note: This is integer division. Any fractional part | |
447 | // of the result is truncated toward zero. | |
448 | BigUnsigned::divide(a, b); | |
449 | // If the result is zero, set the sign to zero. | |
450 | if (len == 0) | |
451 | sign = zero; | |
452 | } | |
453 | ||
454 | // Modular reduction | |
455 | void BigInteger::modulo(const BigInteger &a, const BigInteger &b) { | |
456 | /* Note that the mathematical definition of mod is somewhat | |
457 | * different from the way the normal C++ % operator behaves. | |
458 | * This function does it the mathematical way. */ | |
459 | // Block unsafe calls | |
460 | if (this == &a || this == &b) | |
461 | throw "BigInteger::modulo: One of the arguments is the invoked object"; | |
462 | // If b is zero, copy a and return. By the mathematical definition, | |
463 | // x mod 0 = x, though the normal C++ % would throw an exception. | |
464 | if (b.len == 0) { | |
465 | operator =(a); | |
466 | return; | |
467 | // If a is zero, copy zero and return. | |
468 | } else if (a.sign == zero) { | |
469 | sign = zero; | |
470 | len = 0; | |
471 | return; | |
472 | } | |
473 | // Perform modular reduction on the magnitudes | |
474 | BigUnsigned::modulo(a, b); | |
475 | // If the result is zero, set the sign to zero. | |
476 | if (len == 0) | |
477 | sign = zero; | |
478 | else { | |
479 | /* If necessary, flip the result over zero so that it has the | |
480 | * same sign as the modulus (by the mathematical definition). | |
481 | * The normal C++ % does not perform this step and always | |
482 | * takes the sign of the first input. */ | |
483 | if (a.sign != b.sign) { | |
484 | BigUnsigned temp(*this); | |
485 | BigUnsigned::subtract(b, temp); | |
486 | } | |
487 | sign = b.sign; | |
488 | } | |
489 | } | |
490 | ||
491 | // Negation | |
492 | void BigInteger::negate(const BigInteger &a) { | |
493 | // Block unsafe calls | |
494 | if (this == &a) | |
495 | throw "BigInteger::negate: The argument is the invoked object"; | |
496 | // Copy a's magnitude | |
497 | BigUnsigned::operator =(a); | |
498 | // Copy the opposite of a.sign | |
499 | sign = Sign(-a.sign); | |
500 | } | |
501 | ||
502 | // INCREMENT/DECREMENT OPERATORS | |
503 | ||
504 | // Prefix increment | |
505 | void BigInteger::operator ++() { | |
506 | switch (sign) { | |
507 | case zero: | |
508 | allocate(1); | |
509 | sign = positive; | |
510 | len = 1; | |
511 | *blk = 1; | |
512 | break; | |
513 | case positive: | |
514 | BigUnsigned::operator ++(); | |
515 | break; | |
516 | case negative: | |
517 | BigUnsigned::operator --(); | |
518 | if (len == 0) | |
519 | sign = zero; | |
520 | break; | |
521 | } | |
522 | } | |
523 | ||
524 | // Postfix increment: same as prefix | |
525 | void BigInteger::operator ++(int) { | |
526 | operator ++(); | |
527 | } | |
528 | ||
529 | // Prefix decrement | |
530 | void BigInteger::operator --() { | |
531 | switch (sign) { | |
532 | case zero: | |
533 | allocate(1); | |
534 | sign = negative; | |
535 | len = 1; | |
536 | *blk = 1; | |
537 | break; | |
538 | case negative: | |
539 | BigUnsigned::operator ++(); | |
540 | break; | |
541 | case positive: | |
542 | BigUnsigned::operator --(); | |
543 | if (len == 0) | |
544 | sign = zero; | |
545 | break; | |
546 | } | |
547 | } | |
548 | ||
549 | // Postfix decrement: same as prefix | |
550 | void BigInteger::operator --(int) { | |
551 | operator --(); | |
552 | } | |
553 |