Commit | Line | Data |
---|---|---|
05780f4b MM |
1 | /* |
2 | * Matt McCutchen's Big Integer Library | |
3 | * http://mysite.verizon.net/mccutchen/bigint/ | |
4 | */ | |
5 | ||
b3fe29df MM |
6 | /* |
7 | * Milan Tomic had trouble compiling this file on Microsoft | |
8 | * Visual C++ 6 because, in the libraries that come with | |
9 | * Visual C++ 6, the `std::string::push_back' method apparently | |
10 | * does not exist. To get around the problem, I rewrote | |
11 | * `BigUnsignedInABase::operator std::string' (at the bottom | |
12 | * of this file) so it doesn't use `push_back'. | |
13 | */ | |
14 | ||
05780f4b | 15 | #include "BigUnsignedInABase.hh" |
e257a1b2 | 16 | #include <iostream> |
05780f4b MM |
17 | |
18 | namespace { | |
19 | unsigned int bitLen(unsigned int x) { | |
20 | unsigned int len = 0; | |
21 | while (x > 0) { | |
22 | x >>= 1; | |
23 | len++; | |
24 | } | |
25 | return len; | |
26 | } | |
27 | unsigned int ceilingDiv(unsigned int a, unsigned int b) { | |
28 | return (a + b - 1) / b; | |
29 | } | |
30 | } | |
e257a1b2 MM |
31 | /*std::cout << "((( BigUnsigned ==> BigUnsignedInABase\n"; |
32 | std::cout << "[ Parameter BigUnsigned @ " << (void *)(NumberlikeArray<BigUnsigned::Blk> *)(&x) | |
33 | << ",\nresulting BigUnsignedInABase @ " << (void *)(NumberlikeArray<Digit> *)(this) << "]" << std::endl;*/ | |
05780f4b | 34 | BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { |
2f145f11 | 35 | |
05780f4b MM |
36 | // Check the base |
37 | if (base < 2) | |
38 | throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2"; | |
39 | // Save the base. | |
40 | // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. | |
41 | this->base = base; | |
42 | ||
43 | // Get an upper bound on how much space we need | |
4efbb076 | 44 | int maxBitLenOfX = x.getLength() * BigUnsigned::N; |
05780f4b MM |
45 | int minBitsPerDigit = bitLen(base) - 1; |
46 | int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); | |
2f145f11 MM |
47 | len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'. |
48 | allocate(len); // Get the space | |
05780f4b MM |
49 | |
50 | BigUnsigned x2(x), buBase(base); | |
51 | Index digitNum = 0; | |
52 | ||
53 | while (!x2.isZero()) { | |
54 | // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'. | |
55 | BigUnsigned lastDigit(x2); | |
56 | lastDigit.divideWithRemainder(buBase, x2); | |
57 | // Save the digit. | |
58 | blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter | |
59 | // Move on. We can't run out of room: we figured it out above. | |
60 | digitNum++; | |
61 | } | |
62 | ||
2f145f11 | 63 | // Save the actual length. |
05780f4b | 64 | len = digitNum; |
e257a1b2 | 65 | /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/ |
05780f4b MM |
66 | } |
67 | ||
68 | BigUnsignedInABase::operator BigUnsigned() const { | |
69 | BigUnsigned ans(0), buBase(base), temp; | |
70 | Index digitNum = len; | |
71 | while (digitNum > 0) { | |
72 | digitNum--; | |
73 | temp.multiply(ans, buBase); | |
74 | ans.add(temp, BigUnsigned(blk[digitNum])); | |
75 | } | |
76 | return ans; | |
77 | } | |
78 | ||
79 | BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { | |
80 | // Check the base. | |
81 | if (base > 36) | |
82 | throw "BigUnsignedInABase(std::string, Base): The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine."; | |
83 | // Save the base. | |
84 | // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. | |
85 | this->base = base; | |
86 | ||
e257a1b2 | 87 | len = s.length(); |
05780f4b MM |
88 | allocate(len); |
89 | ||
90 | Index digitNum, symbolNumInString; | |
91 | for (digitNum = 0; digitNum < len; digitNum++) { | |
92 | symbolNumInString = len - 1 - digitNum; | |
93 | char theSymbol = s[symbolNumInString]; | |
94 | if (theSymbol >= '0' && theSymbol <= '9') | |
95 | blk[digitNum] = theSymbol - '0'; | |
96 | else if (theSymbol >= 'A' && theSymbol <= 'Z') | |
97 | blk[digitNum] = theSymbol - 'A' + 10; | |
98 | else if (theSymbol >= 'a' && theSymbol <= 'z') | |
99 | blk[digitNum] = theSymbol - 'a' + 10; | |
100 | else | |
101 | throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted."; | |
102 | } | |
103 | zapLeadingZeros(); | |
104 | } | |
105 | ||
106 | BigUnsignedInABase::operator std::string() const { | |
e257a1b2 | 107 | //std::cout << "((( BigUnsignedInABase ==> std::string\n"; |
05780f4b MM |
108 | if (base > 36) |
109 | throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine."; | |
110 | if (len == 0) | |
111 | return std::string("0"); | |
b3fe29df MM |
112 | char *s = new char[len + 1]; |
113 | s[len] = '\0'; | |
05780f4b MM |
114 | Index digitNum, symbolNumInString; |
115 | for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) { | |
116 | digitNum = len - 1 - symbolNumInString; | |
117 | Digit theDigit = blk[digitNum]; | |
118 | if (theDigit < 10) | |
b3fe29df | 119 | s[symbolNumInString] = char('0' + theDigit); |
05780f4b | 120 | else |
b3fe29df | 121 | s[symbolNumInString] = char('A' + theDigit - 10); |
05780f4b | 122 | } |
2f145f11 MM |
123 | std::string s2(s); |
124 | delete s; | |
e257a1b2 | 125 | //std::cout << "BigUnsignedInABase ==> std::string )))\n"; |
2f145f11 | 126 | return s2; |
05780f4b | 127 | } |