bignumberope.hpp

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

#ifndef		_SDL_MATHS_NUMBERS_BIG_NUMBER_OPE_HPP_
#define		_SDL_MATHS_NUMBERS_BIG_NUMBER_OPE_HPP_

#ifndef		_SDL_MATHS_NUMBERS_BIG_NUMBER_HPP_
#error		"must be included by BigNumber.hpp"
#endif

SDL_MATHS_NUMBERS_BEGIN

inline
OutStream&	operator << (OutStream& o, const BigNumber& n)
{
	Int32 curr = n.GetLength() - 1;
	if (n.GetSign() < 0)
	{
		o << '-';
	}
	o << n[curr--];
	while (curr>=0)
	{
		o.fill('0');
		o.width(DIG_COUNT);
		o << n[curr--];
	}
	return o;
}

inline
BigNumber	operator + (const BigNumber& l, const BigNumber& r)
{
	if (l.IsZero())
	{
		return r;
	}

	if (r.IsZero())
	{
		return l;
	}

	if (l.GetSign() == r.GetSign())
	{
		BigNumber	ret(BigNumber::AbsAdd(l, r));
		ret.Sign = l.Sign;
		ret.ZeroAdjust();
		return ret;
	}

	Int32	cmp;
	if ((cmp = BigNumber::AbsCompare(l, r)) > 0)
	{
		BigNumber	ret(BigNumber::AbsSub(l, r));
		ret.Sign = l.Sign;
		ret.ZeroAdjust();
		return ret;
	}
	else if (cmp < 0)
	{
		BigNumber	ret(BigNumber::AbsSub(r, l));
		ret.Sign = r.Sign;
		ret.ZeroAdjust();
		return ret;
	}
	else
	{
		return 0;
	}
}

inline
BigNumber	operator - (const BigNumber& l, const BigNumber& r)
{
	if (l.IsZero())
	{
		return -r;
	}

	if (r.IsZero())
	{
		return l;
	}

	if (l.GetSign() != r.GetSign())
	{
		BigNumber	ret(BigNumber::AbsAdd(l, r));
		ret.Sign = l.Sign;
		ret.ZeroAdjust();
		return ret;
	}

	Int32	cmp;
	if ((cmp = BigNumber::AbsCompare(l, r)) > 0)
	{
		BigNumber	ret(BigNumber::AbsSub(l, r));
		ret.Sign = l.Sign;
		ret.ZeroAdjust();
		return ret;
	}
	else if (cmp < 0)
	{
		BigNumber	ret(BigNumber::AbsSub(r, l));
		ret.Sign = -r.Sign;
		ret.ZeroAdjust();
		return ret;
	}
	else
	{
		return 0;
	}
}

inline
BigNumber	operator * (const BigNumber& l, const BigNumber& r)
{
	Int32	s = l.GetSign() * r.GetSign();

	if (s == 0)
	{
		return 0;
	}

	BigNumber	ret(BigNumber::AbsMul(l, r));
	ret.Sign = s;

	return ret;
}

inline
BigNumber	operator / (const BigNumber& l, const BigNumber& r)
{
	Int32	s = l.GetSign() * r.GetSign();
	Int32	cmp = BigNumber::AbsCompare(l, r);

	if (s == 0 || cmp < 0)
	{
		return 0;
	}

	if (cmp == 0)
	{
		return 1;
	}

	BigNumber	ret(BigNumber::AbsDiv(l, r));
	ret.Sign = s;

	return ret;
}

inline
BigNumber	operator ^ (const BigNumber& l, Int32 n)
{
	BigNumber	ret(1);
	BigNumber	t(l);

	for (;n; n /= 2)
	{
		if (n & 1)
		{
			ret *= t;
		}
		t *= t;
	}

	return ret;
}

inline
BigNumber	operator ^ (const BigNumber& l, BigNumber& n)
{
	BigNumber	ret(1);
	BigNumber	t(l);

	for (;!n.IsZero(); n /= 2)
	{
		if (n[0]&1)
		{
			ret *= t;
		}
		t *= t;
	}

	return ret;
}

inline
BigNumber	operator % (const BigNumber& l, const BigNumber& r)
{
	Int32	s = l.Sign * r.Sign;

	if (s == 0)
	{
		return 0;
	}

	BigNumber ret(l.Buffer(), l.Length, BigNumberData::COPY_DATA);
	BigNumber::AbsDivImpl(ret, r);
	ret.Sign = l.Sign;
	ret.ZeroAdjust();

	return ret;
}

inline
Bool	operator > (const BigNumber& l, const BigNumber& r)
{
	Int32 s1 = l.Sign;
	Int32 s2 = r.Sign;

	if (s1 < 0)
	{
		return s2 < 0 && BigNumber::AbsCompare(l, r) < 0;
	}
	else if (s1 > 0)
	{
		return s2 <= 0 || BigNumber::AbsCompare(l, r) > 0;
	}
	else
	{
		return s2 < 0;
	}
}

inline
Bool	operator < (const BigNumber& l, const BigNumber& r)
{
	Int32 s1 = l.Sign;
	Int32 s2 = r.Sign;

	if (s1 < 0)
	{
		return s2 >= 0 || BigNumber::AbsCompare(l, r) > 0;
	}
	else if (s1 > 0)
	{
		return s2 > 0 && BigNumber::AbsCompare(l, r) < 0;
	}
	else
	{
		return s2 > 0;
	}
}

inline
Bool	operator == (const BigNumber& l, const BigNumber& r)
{
	return l.Sign == r.Sign && BigNumber::AbsCompare(l, r) == 0;
}

inline
Bool	operator >= (const BigNumber& l, const BigNumber& r)
{
	Int32 s1 = l.Sign;
	Int32 s2 = r.Sign;

	if (s1 < 0)
	{
		return s2 < 0 && BigNumber::AbsCompare(l, r) <= 0;
	}
	else if (s1 > 0)
	{
		return s2 <= 0 || BigNumber::AbsCompare(l, r) >= 0;
	}
	else
	{
		return s2 <= 0;
	}
}

inline
Bool	operator <= (const BigNumber& l, const BigNumber& r)
{
	Int32 s1 = l.Sign;
	Int32 s2 = r.Sign;

	if (s1 < 0)
	{
		return s2 >= 0 || BigNumber::AbsCompare(l, r) >= 0;
	}
	else if (s1 > 0)
	{

		return s2 > 0 && BigNumber::AbsCompare(l, r) <= 0;
	}
	else
	{
		return s2 >= 0;
	}
}

inline
BigNumber	GCD(const BigNumber& l, const BigNumber& r)
{
	BigNumber	a(l);
	BigNumber	b(r);
	BigNumber	t;

	while (!b.IsZero())
	{
		t = b;
		b = a % b;
		a = t;
	}

	return a;
}

inline
BigNumber	GCDEX(const BigNumber& p, const BigNumber& m)
{
	BigNumber	d(m), c(p);
	BigNumber	b(1), b1(0);
	BigNumber	q, r, t;

	for (;;)
	{
		q = c / d;
		r = c % d;
		if (r.IsZero()) break;
		t = b1;
		b1 = b;
		b = t - q * b;
		c = d;
		d = r;
	}
	
	return (b % p + p) % p;
}

inline
BigNumber	fabs(const BigNumber& n)
{
	return n.Sign >= 0 ? n : -n;
}

inline
BigNumber	abs(const BigNumber& n)
{
	return n.Sign >= 0 ? n : -n;
}

SDL_MATHS_NUMBERS_END

#endif