2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
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'.
15 #include "BigUnsignedInABase.hh"
19 unsigned int bitLen(unsigned int x) {
27 unsigned int ceilingDiv(unsigned int a, unsigned int b) {
28 return (a + b - 1) / b;
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;*/
34 BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
38 throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
40 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
43 // Get an upper bound on how much space we need
44 int maxBitLenOfX = x.getLength() * BigUnsigned::N;
45 int minBitsPerDigit = bitLen(base) - 1;
46 int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
47 len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'.
48 allocate(len); // Get the space
50 BigUnsigned x2(x), buBase(base);
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);
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.
63 // Save the actual length.
65 /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/
68 BigUnsignedInABase::operator BigUnsigned() const {
69 BigUnsigned ans(0), buBase(base), temp;
71 while (digitNum > 0) {
73 temp.multiply(ans, buBase);
74 ans.add(temp, BigUnsigned(blk[digitNum]));
79 BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
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.";
84 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
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;
101 throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted.";
106 BigUnsignedInABase::operator std::string() const {
107 //std::cout << "((( BigUnsignedInABase ==> std::string\n";
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.";
111 return std::string("0");
112 char *s = new char[len + 1];
114 Index digitNum, symbolNumInString;
115 for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
116 digitNum = len - 1 - symbolNumInString;
117 Digit theDigit = blk[digitNum];
119 s[symbolNumInString] = char('0' + theDigit);
121 s[symbolNumInString] = char('A' + theDigit - 10);
125 //std::cout << "BigUnsignedInABase ==> std::string )))\n";