[bigint/bigint.git] / BigUnsignedInABase.cc

/*
* Matt McCutchen's Big Integer Library
* http://mysite.verizon.net/mccutchen/bigint/
*/

/*
* Milan Tomic had trouble compiling this file on Microsoft
* Visual C++ 6 because, in the libraries that come with
* Visual C++ 6, the `std::string::push_back' method apparently
* does not exist.  To get around the problem, I rewrote
* `BigUnsignedInABase::operator std::string' (at the bottom
* of this file) so it doesn't use `push_back'.
*/

#include "BigUnsignedInABase.hh"
#include <iostream>

namespace {
	unsigned int bitLen(unsigned int x) {
		unsigned int len = 0;
		while (x > 0) {
			x >>= 1;
			len++;
		}
		return len;
	}
	unsigned int ceilingDiv(unsigned int a, unsigned int b) {
		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";
	// Save the base.
	// This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
	this->base = base;
	
	// Get an upper bound on how much space we need
	int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk);
	int minBitsPerDigit = bitLen(base) - 1;
	int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
	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;
	
	while (!x2.isZero()) {
		// Get last digit.  This is like `lastDigit = x2 % buBase, x2 /= buBase'.
		BigUnsigned lastDigit(x2);
		lastDigit.divideWithRemainder(buBase, x2);
		// Save the digit.
		blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter
		// Move on.  We can't run out of room: we figured it out above.
		digitNum++;
	}
	
	// Save the actual length.
	len = digitNum;
	/*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/
}

BigUnsignedInABase::operator BigUnsigned() const {
	BigUnsigned ans(0), buBase(base), temp;
	Index digitNum = len;
	while (digitNum > 0) {
		digitNum--;
		temp.multiply(ans, buBase);
		ans.add(temp, BigUnsigned(blk[digitNum]));
	}
	return ans;
}

BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
	// Check the base.
	if (base > 36)
		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.";
	// Save the base.
	// This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
	this->base = base;
	
	len = s.length();
	allocate(len);
	
	Index digitNum, symbolNumInString;
	for (digitNum = 0; digitNum < len; digitNum++) {
		symbolNumInString = len - 1 - digitNum;
		char theSymbol = s[symbolNumInString];
		if (theSymbol >= '0' && theSymbol <= '9')
			blk[digitNum] = theSymbol - '0';
		else if (theSymbol >= 'A' && theSymbol <= 'Z')
			blk[digitNum] = theSymbol - 'A' + 10;
		else if (theSymbol >= 'a' && theSymbol <= 'z')
			blk[digitNum] = theSymbol - 'a' + 10;
		else
			throw "BigUnsignedInABase(std::string, Base): Bad symbol in input.  Only 0-9, A-Z, a-z are accepted.";
	}
	zapLeadingZeros();
}

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)
		return std::string("0");
	char *s = new char[len + 1];
	s[len] = '\0';
	Index digitNum, symbolNumInString;
	for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
		digitNum = len - 1 - symbolNumInString;
		Digit theDigit = blk[digitNum];
		if (theDigit < 10)
			s[symbolNumInString] = char('0' + theDigit);
		else
			s[symbolNumInString] = char('A' + theDigit - 10);
	}
	std::string s2(s);
	delete s;
	//std::cout << "BigUnsignedInABase ==> std::string )))\n";
	return s2;
}
Commit	Line	Data
05780f4b MM	1	/*
	2	* Matt McCutchen's Big Integer Library
	3	* http://mysite.verizon.net/mccutchen/bigint/
	4	*/
	5
b3fe29df MM	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
05780f4b	15	#include "BigUnsignedInABase.hh"
2f145f11	16	#include <iostream>
05780f4b MM	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	}
2f145f11 MM	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;*/
05780f4b	34	BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
2f145f11	35
05780f4b MM	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);
2f145f11 MM	47	len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'.
2f145f11 MM	48	allocate(len); // Get the space
05780f4b MM	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
2f145f11	63	// Save the actual length.
05780f4b	64	len = digitNum;
2f145f11	65	/std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";/
05780f4b MM	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 {
2f145f11	107	//std::cout << "((( BigUnsignedInABase ==> std::string\n";
05780f4b MM	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");
b3fe29df MM	112	char *s = new char[len + 1];
b3fe29df MM	113	s[len] = '\0';
05780f4b MM	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)
b3fe29df	119	s[symbolNumInString] = char('0' + theDigit);
05780f4b	120	else
b3fe29df	121	s[symbolNumInString] = char('A' + theDigit - 10);
05780f4b	122	}
2f145f11 MM	123	std::string s2(s);
	124	delete s;
	125	//std::cout << "BigUnsignedInABase ==> std::string )))\n";
	126	return s2;
05780f4b	127	}