bignumber.hpp

简单的C++计算库.其中实现了矩阵运算,大数运算.矩阵处理中使用lazy calculate,并且封装常见算法,可以将普通matlab程序用SDL改写.

#ifndef		_SDL_MATHS_NUMBERS_BIG_NUMBER_HPP_
#define		_SDL_MATHS_NUMBERS_BIG_NUMBER_HPP_

SDL_MATHS_NUMBERS_BEGIN

typedef	DataBlock<Int32>	BigNumberData;

const Int32	BIG_NUMBER_BASE	=	10000;
const Int32	DIG_COUNT		=	4;

class	BigNumber
	:	protected	BigNumberData
{

	friend	inline	BigNumber	operator + (const BigNumber& l, const BigNumber& r);
	friend	inline	BigNumber	operator - (const BigNumber& l, const BigNumber& r);
	friend	inline	BigNumber	operator * (const BigNumber& l, const BigNumber& r);
	friend	inline	BigNumber	operator / (const BigNumber& l, const BigNumber& r);
	friend	inline	BigNumber	operator ^ (const BigNumber& l, Int32 n);
	friend	inline	BigNumber	operator ^ (const BigNumber& l, BigNumber& r);
	friend	inline	BigNumber	operator % (const BigNumber& l, const BigNumber& r);
	friend	inline	Bool		operator > (const BigNumber& l, const BigNumber& r);
	friend	inline	Bool		operator < (const BigNumber& l, const BigNumber& r);
	friend	inline	Bool		operator == (const BigNumber& l, const BigNumber& r);
	friend	inline	Bool		operator >= (const BigNumber& l, const BigNumber& r);
	friend	inline	Bool		operator <= (const BigNumber& l, const BigNumber& r);
	friend	inline	OutStream&	operator << (std::ostream& o, const BigNumber& n);

	friend	inline	BigNumber	GCD(const BigNumber& l, const BigNumber& r);
	friend	inline	BigNumber	GCDEX(const BigNumber& p, const BigNumber& m);
	friend	inline	BigNumber	fabs(const BigNumber& n);
	friend	inline	BigNumber	abs(const BigNumber& n);

public:

	typedef	BigNumber	SelfType;

	BigNumber(Int32 value = 0)
	{
		ZeroInit();

		if (value != 0)
		{
			Sign = value > 0 ? 1 : -1;
			if (value < 0)
			{
				value = - value;
			}

			Int32 curr = 0;
			for (;value; value /= BIG_NUMBER_BASE, ++curr)
			{
				BigNumberData::pData[curr] = value % BIG_NUMBER_BASE;
			}
			Length = curr;
		}
	}

	BigNumber(const TCHAR* _pCharNumber)
	{
		ReadCharNumber(_pCharNumber);
	}

	BigNumber(const BigNumber& other)
		:	BigNumberData(other)
	{
		Length		= other.Length;
		Sign		= other.Sign;
	}

	BigNumber(Int32* _pBuff, Int32 size, Int32 copy = BigNumberData::NOT_COPY_DATA, Int32 copy_size = BigNumberData::COPY_ALL)
		:	BigNumberData(_pBuff, size, copy, copy_size),
			Length(size),
			Sign(1)
	{
		if (_pBuff == 0)
		{
			memset(pData, 0, sizeof(Int32) * size);
		}
		ZeroAdjust();
	}

	BigNumber&	operator = (const BigNumber& other)
	{
		if (&other != this)
		{
			BigNumber	temp(other);
			Swap(temp);
		}
		return *this;
	}

	void	Swap(BigNumber& other)
	{
		BigNumberData::Swap(other);
		std::swap(Length, other.Length);
		std::swap(Sign, other.Sign);
	}

	Int32*	Buffer() const
	{
		return BigNumberData::Buffer();
	}

	Int32	GetLength() const
	{
		return Length;
	}

	Int32	GetSign() const
	{
		return Sign;
	}

	void	Neg()
	{
		Sign = -Sign;
	}

	Bool	IsZero() const
	{
		return !GetSign();
	}

	Int32	operator [] (Int32 pos) const
	{
		return BigNumberData::pData[pos];
	}

	Int32&	operator [] (Int32 pos)
	{
		//Dangerous, if pData is shared by another bignumber
		return BigNumberData::pData[pos];
	}

	Int32	Capacity() const
	{
		return BigNumberData::DataSize;
	}

	void	Reserve(Int32 size)
	{
		if (Capacity() < size)
		{
			BigNumberData	temp(size);
			Int32 *	buff = temp.Buffer();
			for (Int32 i = 0; i < Capacity(); ++i)
			{
				buff[i] = BigNumberData::pData[i];
			}
			BigNumberData::Swap(temp);
		}
	}

protected:

	void	ReadCharNumber(const TCHAR* _pCharNumber)
	{
		RT_CONDITION(_pCharNumber != NULL);

		Int32 s = 1;
		Int32 i = 0, j = 0;
		if (_pCharNumber[i] == '-')
		{
			s = -s;
			++i;
		}
		else if (_pCharNumber[i] == '+')
		{
			++i;
		}

		for (j = i; _pCharNumber[j] != '\0'; ++j)
			;
		--j;

		Int32 length = j - i + 1;

		if (length == 0)
		{
			ZeroInit();
			return;
		}

		Int32	size = CalStoreLength(length);

		BigNumberData temp_data(size);
		BigNumberData::Swap(temp_data);

		Int32 * temp = BigNumberData::Buffer();
		Int32	curr = 0;

		while (j >= i)
		{
			Int32 value = 0;
			Int32 count = 0;
			Int32 base = 1;
			while (j >= i && count++ < DIG_COUNT)
			{
				value += base * (_pCharNumber[j--] - '0');
				base *= 10;
			}
			temp[curr++] = value;
		}

		Length = size;
		Sign = 1;
		ZeroAdjust();
	}

	void	ZeroAdjust() const
	{
		int i;
		for (i = Length - 1; i >= 0 && BigNumberData::pData[i] == 0; --i)
			;
		if (i < 0)
		{
			Length = 1;
			Sign = 0;
		}
		else
		{
			Length = i + 1;
		}
	}

private:

	Int32	CalStoreLength(Int32 length)
	{
		Int32 ret = length / DIG_COUNT;
		if (length % DIG_COUNT)
		{
			++ret;
		}
		return ret;
	}

	void	ZeroInit()
	{
		BigNumberData temp_data(4);
		BigNumberData::Swap(temp_data);

		memset(this->Buffer(), 0, sizeof(Int32) * 4);
		Length = 1;
		Sign = 0;
	}

public:

	static	Bool	AbsCompare(const BigNumber& l, const BigNumber& r)
	{
		l.ZeroAdjust();
		r.ZeroAdjust();

		Int32	l_length = l.GetLength();
		Int32	r_length = r.GetLength();

		if (l_length != r_length)
		{
			return l_length - r_length;
		}

		for (--l_length; l_length >= 0 && l[l_length] == r[l_length]; --l_length)
			;

		return l_length >= 0 ? l[l_length] - r[l_length] : 0;
	}

	static	BigNumber	AbsAddImpl(BigNumber& l, const BigNumber& r)
	{
		l.ZeroAdjust();
		r.ZeroAdjust();

		Int32	longer			= l.GetLength();
		Int32	shorter			= r.GetLength();
		Int32*	longer_buffer	= l.Buffer();
		Int32*	shorter_buffer	= r.Buffer();

		RT_CONDITION(longer >= shorter);

		Int32		inc = 0;
		Int32		curr = 0;

		for (; curr < shorter; ++curr)
		{
			inc += longer_buffer[curr] + shorter_buffer[curr];
			longer_buffer[curr] = inc % BIG_NUMBER_BASE;
			inc /= BIG_NUMBER_BASE;
		}

		for (; curr < longer; ++curr)
		{
			Int32 value = longer_buffer[curr] + inc;
			longer_buffer[curr] = value % BIG_NUMBER_BASE;
			inc = value / BIG_NUMBER_BASE;
		}

		if (inc)
		{
			l.Reserve(curr+1);
			l[curr++] = inc;
		}

		l.Length = curr;
		return l;
	}

	static	BigNumber	AbsAdd(const BigNumber& l, const BigNumber& r)
	{
		l.ZeroAdjust();
		r.ZeroAdjust();
		if (l.Length >= r.Length)
		{
			BigNumber	l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);
			return AbsAddImpl(l_temp, r);
		}
		else
		{
			BigNumber	l_temp(r.Buffer(), r.Length, BigNumberData::COPY_DATA);
			return AbsAddImpl(l_temp, l);
		}
	}

	static	BigNumber	AbsSubImpl(BigNumber& l, const BigNumber& r)
	{
		Int32	longer			= l.GetLength();
		Int32	shorter			= r.GetLength();
		Int32*	shorter_buffer	= r.Buffer();
		Int32*	longer_buffer	= l.Buffer();

		(void)longer;

		RT_CONDITION(BigNumber::AbsCompare(l, r) >= 0);

		for (Int32 curr = 0; curr < shorter; ++curr)
		{
			Int32 value = longer_buffer[curr] - shorter_buffer[curr];
			while (value < 0)
			{
				--longer_buffer[curr+1];
				value += BIG_NUMBER_BASE;
			}
			longer_buffer[curr] = value;
		}

		l.ZeroAdjust();

		return l;
	}

	static	BigNumber	AbsSub(const BigNumber& l, const BigNumber& r)
	{
		l.ZeroAdjust();
		r.ZeroAdjust();
		if (l.Length >= r.Length)
		{
			BigNumber	l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);
			return AbsSubImpl(l_temp, r);
		}
		else
		{
			BigNumber	l_temp(r.Buffer(), r.Length, BigNumberData::COPY_DATA);
			return AbsSubImpl(l_temp, l);
		}
	}

	static	BigNumber	AbsMulImpl(const BigNumber& l, const BigNumber& r)
	{
		l.ZeroAdjust();
		r.ZeroAdjust();

		Int32	l_length	= l.GetLength();
		Int32	r_length	= r.GetLength();
		Int32	ret_length	= l_length + r_length;

		BigNumber	ret(NULL, ret_length);

		Int32*	ret_buffer	= ret.Buffer();
		Int32*	l_buffer	= l.Buffer();
		Int32*	r_buffer	= r.Buffer();

		for (Int32 i = 0; i < ret_length; ++i)
		{
			ret_buffer[i] = 0;
		}

		for (Int32 i = 0; i < r_length; ++i)
		{
			Int32 t = r_buffer[i];
			Int32 inc = 0;
			Int32 j = 0;
			for (; j < l_length; ++j)
			{
				inc += t * l_buffer[j] + ret_buffer[i+j];
				ret_buffer[i+j] = inc % BIG_NUMBER_BASE;
				inc /= BIG_NUMBER_BASE;
			}
			for ( ;inc; inc /= BIG_NUMBER_BASE)
			{
				ret_buffer[i+j++] = inc % BIG_NUMBER_BASE;
			}
		}
		ret.Length = ret_length;
		ret.ZeroAdjust();
		return ret;
	}

	static	BigNumber	AbsMul(const BigNumber& l, const BigNumber& r)
	{
		return AbsMulImpl(l, r);
	}

	static	Int32		DoMemMul(Int32* ResultBuff, Int32* LeftBuff, Int32 LeftLength, Int32 RightValue)
	{
		Int32	curr = 0;
		Int32	inc = 0;
		for (; curr < LeftLength; ++curr)
		{
			Int32 value = RightValue * LeftBuff[curr] + inc;
			ResultBuff[curr] = value % BIG_NUMBER_BASE;
			inc = value / BIG_NUMBER_BASE;
		}
		if (inc)
		{
			ResultBuff[curr++] = inc;
		}
		return curr;
	}

	static	Int32		DoSub(Int32* LeftBuff, Int32 hi_l, Int32 lo_l,
							  Int32* RightBuff, Int32 hi_r, Int32 lo_r,
							  Int32 test, Int32* temp)
	{
			int hi2 = DoMemMul(temp+lo_r, RightBuff, hi_r-lo_r+1, test) - 1;

			if (hi2 >= hi_l - lo_l + 1)
			{
				return 0;
			}

			if (hi_l - lo_l == hi2 - lo_r)
			{
				for (Int32 i = hi_l, j = hi2; i >= lo_l; --i, --j)
					{
						if(LeftBuff[i] < temp[j])
						{
							return 0;
						}
						if (LeftBuff[i] > temp[j])
						{
							break;
						}
					}
			}

			for (Int32 i = lo_r, j = lo_l; i <= hi2; ++i, ++j)
			{
				if ((LeftBuff[j] -= temp[i]) < 0)
				{
					LeftBuff[j] += BIG_NUMBER_BASE;
					--LeftBuff[j+1];
				}
			}

			return 1;
	}

	static	BigNumber	AbsDivImpl(BigNumber& remain, const BigNumber& r)
	{
		DataBlock<int>	buffer_data(remain.Length + 5);

		remain.ZeroAdjust();
		r.ZeroAdjust();

		Int32	l_length	= remain.GetLength();
		Int32	r_length	= r.GetLength();
		Int32	ret_length	= l_length - r_length + 1;

		BigNumber	ret(NULL, ret_length);

		Int32*	ret_buffer	= ret.Buffer();
		Int32*	l_buffer	= remain.Buffer();
		Int32*	r_buffer	= r.Buffer();

		Int32	curr = ret_length - 1;
		Int32	hi_l = l_length - 1, lo_l = curr;
		Int32	hi_r = r_length - 1, lo_r = 0;

		for (; curr >= 0; --curr, --lo_l)
		{
			Int32	test;
			if (r_length > 1)
			{
				if (hi_l-lo_l>hi_r-lo_r)
				{
					test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / r_buffer[hi_r];
				}
				else
				{
					test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / (r_buffer[hi_r]*BIG_NUMBER_BASE + r_buffer[hi_r-1]);
				}
			}
			else
			{
				if (hi_l-lo_l+1>1)
				{
					test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / r_buffer[hi_r];
				}
				else
				{
					test = l_buffer[hi_l]/r_buffer[hi_r];
				}
			}

			for( ; test > 0; --test)
			{
				if (BigNumber::DoSub(l_buffer, hi_l, lo_l, r_buffer,  hi_r, lo_r, test, buffer_data.Buffer()))
				{
					break;
				}
			}
			
			for (;l_buffer[hi_l] == 0 && hi_l >= lo_l; --hi_l)
				;

			ret_buffer[curr] = test;
		}

		ret.Length = ret_length;
		ret.ZeroAdjust();
		remain.ZeroAdjust();
		return ret;
	}

	static	BigNumber	AbsDiv(const BigNumber& l, const BigNumber& r)
	{
		BigNumber	l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);

		return AbsDivImpl(l_temp, r);
	}

public:

	BigNumber	operator - () const
	{
		BigNumber ret(*this);
		ret.Neg();
		return ret;
	}

	BigNumber	operator + () const
	{
		return *this;
	}

	BigNumber&	operator += (const BigNumber& other)
	{
		*this = *this + other;
		return *this;
	}

	BigNumber&	operator -= (const BigNumber& other)
	{
		*this = *this - other;
		return *this;
	}

	BigNumber&	operator *= (const BigNumber& other)
	{
		*this = *this * other;
		return *this;
	}

	BigNumber&	operator /= (const BigNumber& other)
	{
		*this = *this / other;
		return *this;
	}

	BigNumber&	operator %= (const BigNumber& other)
	{
		*this = *this % other;
		return *this;
	}

	BigNumber&	operator ^= (Int32 n)
	{
		*this = *this ^ n;
		return *this;
	}

	BigNumber& operator ++ ()
	{
		*this = *this + 1;
		return *this;
	}

	BigNumber operator ++ (int)
	{
		BigNumber ret(*this);
		*this = *this + 1;
		return ret;
	}

	BigNumber& operator -- ()
	{
		*this = *this - 1;
		return *this;
	}

	BigNumber operator -- (int)
	{
		BigNumber ret(*this);
		*this = *this - 1;
		return ret;
	}

protected:

	mutable	Int32	Length;
	mutable	Int32	Sign;

};

SDL_MATHS_NUMBERS_END

SDL_BEGIN
	DEC_TYPE_TRAIT(SDL_MATHS_NS::SDL_MATHS_NUMBERS_NS::BigNumber, true, true)
SDL_END

#include		"BigNumberOpe.hpp"

#endif