2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
6 #include "BigUnsignedInABase.hh"
9 unsigned int bitLen(unsigned int x) {
17 unsigned int ceilingDiv(unsigned int a, unsigned int b) {
18 return (a + b - 1) / b;
22 BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
25 throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
27 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
30 // Get an upper bound on how much space we need
31 int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk);
32 int minBitsPerDigit = bitLen(base) - 1;
33 int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
34 allocate(maxDigitLenOfX); // Get the space
36 BigUnsigned x2(x), buBase(base);
39 while (!x2.isZero()) {
40 // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'.
41 BigUnsigned lastDigit(x2);
42 lastDigit.divideWithRemainder(buBase, x2);
44 blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter
45 // Move on. We can't run out of room: we figured it out above.
49 // Save the eventual length.
53 BigUnsignedInABase::operator BigUnsigned() const {
54 BigUnsigned ans(0), buBase(base), temp;
56 while (digitNum > 0) {
58 temp.multiply(ans, buBase);
59 ans.add(temp, BigUnsigned(blk[digitNum]));
64 BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
67 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.";
69 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
75 Index digitNum, symbolNumInString;
76 for (digitNum = 0; digitNum < len; digitNum++) {
77 symbolNumInString = len - 1 - digitNum;
78 char theSymbol = s[symbolNumInString];
79 if (theSymbol >= '0' && theSymbol <= '9')
80 blk[digitNum] = theSymbol - '0';
81 else if (theSymbol >= 'A' && theSymbol <= 'Z')
82 blk[digitNum] = theSymbol - 'A' + 10;
83 else if (theSymbol >= 'a' && theSymbol <= 'z')
84 blk[digitNum] = theSymbol - 'a' + 10;
86 throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted.";
91 BigUnsignedInABase::operator std::string() const {
93 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.";
95 return std::string("0");
98 Index digitNum, symbolNumInString;
99 for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
100 digitNum = len - 1 - symbolNumInString;
101 Digit theDigit = blk[digitNum];
103 s.push_back(char('0' + theDigit));
105 s.push_back(char('A' + theDigit - 10));