sign = zero; // NumberlikeArray did the rest
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
}
}
BigInteger::BigInteger(long x) {
if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
} else if (x < 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = negative;
len = 1;
- *blk = Blk(-x);
+ blk[0] = Blk(-x);
} else
sign = zero;
}
sign = zero;
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
}
}
BigInteger::BigInteger(int x) {
if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
} else if (x < 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = negative;
len = 1;
- *blk = Blk(-x);
+ blk[0] = Blk(-x);
} else
sign = zero;
}
sign = zero;
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
}
}
BigInteger::BigInteger(short x) {
if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = positive;
len = 1;
- *blk = Blk(x);
+ blk[0] = Blk(x);
} else if (x < 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
sign = negative;
len = 1;
- *blk = Blk(-x);
+ blk[0] = Blk(-x);
} else
sign = zero;
}
return 0;
case positive:
if (len == 1)
- return *blk;
+ return blk[0];
else
throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long";
case negative:
case zero:
return 0;
case positive:
- if (len == 1 && (*blk & ~lMask) == 0)
- return long(*blk);
+ if (len == 1 && (blk[0] & ~lMask) == 0)
+ return long(blk[0]);
else
throw "BigInteger operator long() const: Value is too big for a long";
case negative:
- if (len == 1 && (*blk & ~lMask) == 0)
- return -long(*blk);
+ if (len == 1 && (blk[0] & ~lMask) == 0)
+ return -long(blk[0]);
else
throw "BigInteger operator long() const: Value is too big for a long";
default:
case zero:
return 0;
case positive:
- if (len == 1 && (*blk & ~uiMask) == 0)
- return (unsigned int)(*blk);
+ if (len == 1 && (blk[0] & ~uiMask) == 0)
+ return (unsigned int)(blk[0]);
else
throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int";
case negative:
case zero:
return 0;
case positive:
- if (len == 1 && (*blk & ~iMask) == 0)
- return int(*blk);
+ if (len == 1 && (blk[0] & ~iMask) == 0)
+ return int(blk[0]);
else
throw "BigInteger operator int() const: Value is too big for an int";
case negative:
- if (len == 1 && (*blk & ~iMask) == 0)
- return -int(*blk);
+ if (len == 1 && (blk[0] & ~iMask) == 0)
+ return -int(blk[0]);
else
throw "BigInteger operator int() const: Value is too big for an int";
default:
case zero:
return 0;
case positive:
- if (len == 1 && (*blk & ~usMask) == 0)
- return (unsigned short)(*blk);
+ if (len == 1 && (blk[0] & ~usMask) == 0)
+ return (unsigned short)(blk[0]);
else
throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short";
case negative:
case zero:
return 0;
case positive:
- if (len == 1 && (*blk & ~sMask) == 0)
- return short(*blk);
+ if (len == 1 && (blk[0] & ~sMask) == 0)
+ return short(blk[0]);
else
throw "BigInteger operator short() const: Value is too big for a short";
case negative:
- if (len == 1 && (*blk & ~sMask) == 0)
- return -short(*blk);
+ if (len == 1 && (blk[0] & ~sMask) == 0)
+ return -short(blk[0]);
else
throw "BigInteger operator short() const: Value is too big for a short";
default:
allocate(1);
sign = positive;
len = 1;
- *blk = 1;
+ blk[0] = 1;
break;
case positive:
BigUnsigned::operator ++();
allocate(1);
sign = negative;
len = 1;
- *blk = 1;
+ blk[0] = 1;
break;
case negative:
BigUnsigned::operator ++();
* Since 2005.01.06, NumberlikeArray uses `NULL' rather
* than a real array if one of zero length is needed.
* These constructors implicitly call NumberlikeArray's
-* default constructor, which sets `blk = NULL, cap = len = 0'.
+* default constructor, which sets `blk2 = NULL, cap = len = 0'.
* So if the input number is zero, they can just return.
* See remarks in `NumberlikeArray.hh'.
*/
; // NumberlikeArray already did all the work
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
;
else {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
}
;
else if (x > 0) {
cap = 1;
- blk = new Blk[1];
+ blk2 = new Blk[1];
len = 1;
blk[0] = Blk(x);
} else
if (this == &b || &q == &b || this == &q)
throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
+ /*std::cout << "((( divideWithRemainder\n[ Dumps:\n*this:\n";
+ dump();
+ std::cout << "b:\n";
+ b.dump();
+ std::cout << "q:\n";
+ q.dump();
+ std::cout << "]\n";*/
+
/*
* Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
* different from the way the normal C++ % operator behaves in the case of division by 0.
Blk bHigh, temp;
bool borrowIn, borrowOut;
- // Make sure we have an extra zero block just past the value,
- // but don't increase the logical length. A shifted subtraction
- // (for example, subtracting 1 << 2 from 4) might stick into
- // this block.
- allocateAndCopy(len + 1);
- blk[len] = 0;
+ /*
+ * Make sure we have an extra zero block just past the value.
+ * A shifted subtraction (for example, subtracting 1 << 2 from 4)
+ * might stick into this block.
+ *
+ * In earlier versions, `len' was not increased. But then Milan Tomic
+ * found out-of-bounds memory accesses. In investigating the problem,
+ * I got tons of warnings in this routine, which I should have expected.
+ * I decided to make the extra block logically part of the number so it
+ * would not cause confusion in the future.
+ */
+ Index origLen = len; // original length
+ len++; // increased to avoid memory management worries
+ allocateAndCopy(len);
+ blk[origLen] = 0;
// work2 holds part of the result of a subtraction.
// (There's no work1. The name work2 is from a previous version.)
- Blk *work2 = new Blk[len];
+ Blk *work2 = new Blk[origLen];
// Set preliminary length for quotient and make room
- q.len = len - b.len + 1;
+ q.len = origLen - b.len + 1;
q.allocate(q.len);
// Zero out the quotient
for (i = 0; i < q.len; i++)
borrowIn = borrowOut;
j++;
k++;
- for (; k < len && borrowIn; j++, k++) {
+ for (; k < origLen && borrowIn; j++, k++) {
borrowIn = (blk[k] == 0);
work2[j] = blk[k] - 1;
}
<< "\nlast block of quotient: " << q.getBlock(0)
<< "\nlength of remainder: " << len
<< "\nlast block of remainder: " << getBlock(0)
- << std::endl; */
+ << std::endl;
+
+ std::cout << "[ Dumps:\n*this:\n";
+ dump();
+ std::cout << "b:\n";
+ b.dump();
+ std::cout << "q:\n";
+ q.dump();
+ std::cout << "]\ndivideWithRemainder )))\n"; */
}
// Bitwise and
*/
#include "BigUnsignedInABase.hh"
+#include <iostream>
namespace {
unsigned int bitLen(unsigned int x) {
return (a + b - 1) / b;
}
}
-
+ /*std::cout << "((( BigUnsigned ==> BigUnsignedInABase\n";
+ std::cout << "[ Parameter BigUnsigned @ " << (void *)(NumberlikeArray<BigUnsigned::Blk> *)(&x)
+ << ",\nresulting BigUnsignedInABase @ " << (void *)(NumberlikeArray<Digit> *)(this) << "]" << std::endl;*/
BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
+
// Check the base
if (base < 2)
throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk);
int minBitsPerDigit = bitLen(base) - 1;
int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
- allocate(maxDigitLenOfX); // Get the space
+ len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'.
+ allocate(len); // Get the space
BigUnsigned x2(x), buBase(base);
Index digitNum = 0;
digitNum++;
}
- // Save the eventual length.
+ // Save the actual length.
len = digitNum;
+ /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/
}
BigUnsignedInABase::operator BigUnsigned() const {
}
BigUnsignedInABase::operator std::string() const {
+ //std::cout << "((( BigUnsignedInABase ==> std::string\n";
if (base > 36)
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.";
if (len == 0)
else
s[symbolNumInString] = char('A' + theDigit - 10);
}
- return std::string(s);
+ std::string s2(s);
+ delete s;
+ //std::cout << "BigUnsignedInABase ==> std::string )))\n";
+ return s2;
}
* NumberlikeArray< whatever >::getLength;
*/
+/*debug*/
+#include <iostream>
+
template <class Blk>
class NumberlikeArray {
public:
// FIELDS
Index cap; // The current allocated capacity of this NumberlikeArray (in blocks)
Index len; // The actual length of the value stored in this NumberlikeArray (in blocks)
- Blk *blk; // Dynamically allocated array of the blocks
+ Blk *blk2; // Dynamically allocated array of the blocks
+
+ static Blk x; // trash that [] can return for out-of-range requests
+
+ void dump() const {
+ std::cout << "Dumping NumberlikeArray @ " << (void *)(this) << '\n';
+ std::cout << "Length " << (len) << ", capacity " << (cap) << '\n';
+ for (unsigned int i = 0; i < len; i++) {
+ std::cout << "Block " << i << ":" << blk2[i] << '\n';
+ }
+ }
+
+ struct BoundsCheckingBlk {
+ const NumberlikeArray *na;
+ BoundsCheckingBlk(NumberlikeArray *na) {
+ this->na = na;
+ }
+ Blk & operator [](Index index) const {
+ if (index >= na->len) {
+ std::cout << "== Out-of-bounds access to block " << index << ". Affected NumberlikeArray: ==\n";
+ na->dump();
+ std::cout << "== End of dump. ==" << std::endl;
+ return x;
+ } else
+ return na->blk2[index];
+ } // dangerous because it allows ``always writable'', but OK for now
+ /*const Blk & operator [](Index index) const {
+ if (index >= na->len)
+ std::cout << "OUT OF BOUNDS! Length " << (na->len) << ", accessed " << index << std::endl;
+ else
+ return na->blk[index];
+ }*/
+ /*operator Blk * () {
+ return na->blk2;
+ }*/
+ };
+
+ BoundsCheckingBlk blk;
+
/*
* Change made on 2005.01.06:
*
*/
// MANAGEMENT
- NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity
- blk = (cap > 0) ? (new Blk[cap]) : NULL;
+ NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity
+ blk2 = (cap > 0) ? (new Blk[cap]) : NULL;
}
void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents
void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents
* created a real `new'-allocated zero-length array. This array would then be lost,
* causing a small but annoying memory leak.
*/
- NumberlikeArray() : cap(0), len(0) {
- blk = NULL;
+ NumberlikeArray() : cap(0), len(0), blk(this) {
+ blk2 = NULL;
}
NumberlikeArray(const NumberlikeArray<Blk> &x); // Copy constructor
void operator=(const NumberlikeArray<Blk> &x); // Assignment operator
NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks
~NumberlikeArray() { // Destructor
- delete [] blk; // Does nothing and causes no error if `blk' is null.
+ delete [] blk2; // Does nothing and causes no error if `blk' is null.
}
// PICKING APART
* so other files including NumberlikeArray will be able to generate real definitions.
*/
+template <class Blk>
+Blk NumberlikeArray<Blk>::x = 0;
+
// MANAGEMENT
// This routine is called to ensure the array is at least a
// If the requested capacity is more than the current capacity...
if (c > cap) {
// Delete the old number array
- delete [] blk;
+ delete [] blk2;
// Allocate the new array
cap = c;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
}
}
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {
// If the requested capacity is more than the current capacity...
if (c > cap) {
- Blk *oldBlk = blk;
+ Blk *oldBlk = blk2;
// Allocate the new number array
cap = c;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy number blocks
Index i;
for (i = 0; i < len; i++)
// Copy constructor
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len) {
+NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x) : len(x.len), blk(this) {
// Create array
cap = len;
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; i++)
// Constructor from an array of blocks
template <class Blk>
-NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) {
+NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) {
// Create array
- blk = new Blk[cap];
+ blk2 = new Blk[cap];
// Copy blocks
Index i;
for (i = 0; i < len; i++)
BigInteger c(a); // Copy a BigInteger.
+ std::cout << "here 0" << std::endl;
+
BigInteger d(-314159265); // c is -314159265. The `int' literal is converted to a BigInteger.
// Ahem: that's too big to be an `int' literal (or even a `long' literal)!
// Disillusion yourself now -- this won't compile.
//BigInteger e(3141592653589793238462643383279);
+ std::cout << "here 1" << std::endl;
+
std::string s("3141592653589793238462643383279");
BigInteger f = easyStringToBI(s);
// Ah. The string is converted to a BigInteger, and strings can be as long as you want.
+ std::cout << "here 2" << std::endl;
+
std::string s2 = easyBItoString(f); // You can convert the other way too.
+ std::cout << "here 3" << std::endl;
+
std::cout << f << std::endl; // f is stringified and send to std::cout.
+ std::cout << "here 4" << std::endl;
+
/*
* Let's do some math!
*
std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h)
<< '\n' << (g / h) << '\n' << (g % h) << std::endl;
+ std::cout << "here 5" << std::endl;
+
BigInteger i(5), j(10), k;
// These two lines do the same thing: k is set to a BigInteger containing 15.
k = i + j;
k.add(i, j);
+ std::cout << "here 6" << std::endl;
+
// Let's do some heavy lifting.
std::cout << "Powers of 3" << std::endl;
std::cout << "How many do you want?" << std::endl;
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff