BigUnsignedInABase.cc

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   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
  15 #include "BigUnsignedInABase.hh"
  16 #include <iostream>
  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 }
  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) {
  35
  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
  44         int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk);
  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
  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
  63         // Save the actual length.
  64         len = digitNum;
  65         /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/
  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
  87         len = s.length();
  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 {
 107         //std::cout << "((( BigUnsignedInABase ==> std::string\n";
 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");
 112         char *s = new char[len + 1];
 113         s[len] = '\0';
 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)
 119                         s[symbolNumInString] = char('0' + theDigit);
 120                 else
 121                         s[symbolNumInString] = char('A' + theDigit - 10);
 122         }
 123         std::string s2(s);
 124         delete s;
 125         //std::cout << "BigUnsignedInABase ==> std::string )))\n";
 126         return s2;
 127 }