2 * Matt McCutchen's Big Integer Library
3 * http://mysite.verizon.net/mccutchen/bigint/
6 #ifndef BIGUNSIGNEDINABASE
7 #define BIGUNSIGNEDINABASE
9 #include "NumberlikeArray.hh"
10 #include "BigUnsigned.hh"
14 * A BigUnsignedInABase object represents a nonnegative
15 * integer of size limited only by available memory,
16 * represented in a user-specified base that can fit in
17 * an `unsigned short' (most can, and this saves memory).
19 * BigUnsignedInABase is intended as an intermediary class
20 * with little functionality of its own. BigUnsignedInABase
21 * objects can be constructed from, and converted to,
22 * BigUnsigneds (requiring multiplication, mods, etc.) and
23 * `std::string's (by switching digit values for appropriate
26 * BigUnsignedInABase is similar to BigUnsigned. Note the following:
28 * (1) They represent the number in exactly the same way, except
29 * that BigUnsignedInABase uses ``digits'' (or Digit) where BigUnsigned uses
30 * ``blocks'' (or Blk).
32 * (2) Both use the management features of NumberlikeArray. (In fact,
33 * my desire to add a BigUnsignedInABase class without duplicating a
34 * lot of code led me to introduce NumberlikeArray.)
36 * (3) The only arithmetic operation supported by BigUnsignedInABase
37 * is an equality test. Use BigUnsigned for arithmetic.
40 class BigUnsignedInABase : protected NumberlikeArray<unsigned short> {
44 typedef unsigned short Digit; // The digit type that BigUnsignedInABases are built from
49 Base base; // The base of this BigUnsignedInABase
53 // These members generally defer to those in NumberlikeArray, possibly with slight changes.
54 // It might be nice if one could request that constructors be inherited in C++.
56 BigUnsignedInABase(int, Index c) : NumberlikeArray<Digit>(0, c) {} // Creates a BigUnsignedInABase with a capacity
58 void zapLeadingZeros() { // Decreases len to eliminate leading zeros
59 while (len > 0 && blk[len - 1] == 0)
63 //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
64 //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents
67 BigUnsignedInABase() : NumberlikeArray<Digit>(), base(2) {} // Default constructor (value is 0 in base 2)
68 BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray<Digit>(x), base(x.base) {} // Copy constructor
70 void operator =(const BigUnsignedInABase &x) { // Assignment operator
71 NumberlikeArray<Digit>::operator =(x);
75 BigUnsignedInABase(const Digit *d, Index l) : NumberlikeArray<Digit>(d, l) { // Constructor from an array of digits
79 // LINKS TO BIGUNSIGNED
80 BigUnsignedInABase(const BigUnsigned &x, Base base);
81 operator BigUnsigned() const;
85 * These use the symbols ``0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'' to represent
86 * digits of 0 through 35. When parsing strings, lowercase is also accepted.
88 * All string representations are big-endian (big-place-value digits first).
89 * (Computer scientists have adopted zero-based counting; why can't they
90 * tolerate little-endian numbers? It makes a lot of sense!)
92 * No string representation has a ``base indicator'' like ``0x''.
94 * An exception is made for zero: it is converted to ``0'' and not the empty string.
96 * If you want different conventions, write your
97 * own routines to go between BigUnsignedInABase and strings. It's not hard.
99 operator std::string() const;
100 BigUnsignedInABase(const std::string &s, Base base);
103 // These accessors can be used to get the pieces of the number
105 Base getBase() const { return base; }
106 NumberlikeArray<Digit>::getCapacity; // (NlA)
107 NumberlikeArray<Digit>::getLength; // (NlA)
108 // Note that getDigit returns 0 if the digit index is beyond the length of the number.
109 // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left.
110 Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; }
111 // Note how we replace one level of abstraction with another.
112 bool isZero() const { return NumberlikeArray<Digit>::isEmpty(); } // Often convenient for loops
117 bool operator ==(const BigUnsignedInABase &x) const {
118 return base == x.base && NumberlikeArray<Digit>::operator ==(x);
120 bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); }