
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                      Long number - multiplication                         //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#include "..\include.h"

// factorial cache (cache 10!, 20!, 30!, ... 10000!), total memory of cache: 7MB
#define FACTSCALE	10		// scale of cache
#define FACTNUM		1000	// max. entries in cache
#define FACTMAX		(FACTSCALE*FACTNUM) // max. value in cache buffer
bignum FactCache[FACTNUM];	// factorial cache
int FactNum = 0;			// number of cached factorials
int FactMem = 0;			// size of factorial cache buffer

/* Required bytes of integer part:
100!: 9*8 = 72 B = 158 dig (3 us)
200!: 20*8 = 160 B = 375 dig (10 us)
500!: 59*8 = 472 B = 1135 dig (40 us)
1000!: 134*8 = 1072 B = 2568 dig (140 us)
2000!: 298*8 = 2384 B = 5736 dig (600 us)
5000!: 848*8 = 6784 B = 16326 dig (3.5 ms)
10000!: 1851*8 = 14808 B = 35660 dig (15 ms)
20000!: 4015*8 = 31210 B = 77338 dig (66 ms)
50000!: 11069*8 = 88552 B = 213237 dig (440 ms)
100000!: 23699*8 = 189592 B	= 456574 dig (2 sec)
200000!: 50522*8 = 404176 B = 973351 dig (8 sec)
500000!: 136632*8 = 1093056 B = 2632342 dig (1 min)
1000000!: 288889*8 = 2311112 B = 5565709 dig (5 min)
*/

///////////////////////////////////////////////////////////////////////////////
// update factorial cache (num=number of entries)

void FactCacheUpdate(int num)
{
	if (FactNum < num)
	{
		// get temporary number
		int ti = GetBigTemp();
		bignum* t = &BigTempNum[ti];
		t->SetMaxSize(FACTMAX*3, 0, false);

		// initial state
		int i = 1;
		t->Set1();
		if (FactNum > 0)
		{
			t->Copy(FactCache[FactNum-1]);
			i = FactNum*FACTSCALE + 1;
		}

		// update cache
		while (FactNum < num)
		{
			int j;
			for (j = FACTSCALE; j > 0; j--)
			{
				t->MulU(i);
				i++;
			}
			FactMem += (int)t->IntSize();
			FactCache[FactNum].SetMaxSize(t->IntSize(), 0);
			FactCache[FactNum].Copy(*t);
			FactNum++;
		}

		// free temporary number
		FreeBigTemp(ti);
	}
}

///////////////////////////////////////////////////////////////////////////////
// mul 2 numbers, store result here

void bignum::Mul(const bignum& num1, const bignum& num2)
{
	// special cases
	if (num1.Equ0() || num2.Equ0()) { this->Set0(); return; }
	if (num1.Equ1()) { this->Copy(num2); return; }
	if (num2.Equ1()) { this->Copy(num1); return; }
	if (num1.EquM1()) { this->Neg(num2); return; }
	if (num2.EquM1()) { this->Neg(num1); return; }

	// limits of integer part
	bint len1 = num1.m_IntNum;
	bint len2 = num2.m_IntNum;
	bint len = len1 + len2;

	// limits of decimal part
	bint dec1 = num1.m_DecNum;
	bint dec2 = num2.m_DecNum;
	bint dec = dec1 + dec2;

	// prepare destination number
	int n0inx = -1;
	bignum* n0 = this;
	if ((len > m_IntMax) || (dec > m_DecMax))
	{
		n0inx = GetBigTemp();
		n0 = &BigTempNum[n0inx];
		n0->SetMaxSize(len*BIGSIZE, dec*BIGSIZE, false);
	}
	bint tot1 = dec1 + len1;
	bint tot2 = dec2 + len2;
	n0->m_IntNum = len;
	n0->m_DecNum = dec;
	bint tot = dec + len;

	// prepare 1st source
	int n1inx = -1;
	const bignum* n1 = &num1;
	if ((n1 == n0) || num1.m_IsNeg)
	{
		n1inx = GetBigTemp();
		bignum* n1b = &BigTempNum[n1inx];
		n1b->SetMaxSize(len1*BIGSIZE, dec1*BIGSIZE, false);

		if (num1.m_IsNeg)
			n1b->Neg(num1);
		else
			n1b->Copy(num1);
		n1 = n1b;
	}

	// prepare 2nd source
	int n2inx = -1;
	const bignum* n2 = &num2;
	if ((n2 == n0) || num2.m_IsNeg)
	{
		if (n2 == &num1)
		{
			n2 = n1;
		}
		else
		{
			n2inx = GetBigTemp();
			bignum* n2b = &BigTempNum[n2inx];
			n2b->SetMaxSize(len2*BIGSIZE, dec2*BIGSIZE, false);

			if (num2.m_IsNeg)
				n2b->Neg(num2);
			else
				n2b->Copy(num2);
			n2 = n2b;
		}
	}

	// multiply
	buint carry = 0;
	const buint* s1 = n1->Base(-dec1);
	const buint* s2 = n2->Base(-dec2);
	buint* d = n0->Base(-dec);
	bint n;
	if (tot1 > tot2)
	{
		n = tot2;
		if (n > 0)
		{
			d[tot1] = n0->MulStr(0, *s2, d, s1, tot1);

			for (n--; n > 0; n--)
			{
				s2++;
				d++;
				d[tot1] = n0->MulAddStr(0, *s2, d, s1, tot1);
			}
		}
	}
	else
	{
		n = tot1;
		if (n > 0)
		{
			// square
			if ((s1 == s2) && (tot1 == tot2))
			{
				n0->SqrStr(d, s1, tot1);
			}
			else
			{
				d[tot2] = n0->MulStr(0, *s1, d, s2, tot2);

				for (n--; n > 0; n--)
				{
					s1++;
					d++;
					d[tot2] = n0->MulAddStr(0, *s1, d, s2, tot2);
				}
			}
		}
	}

	// data reduction
	n0->m_IsNeg = false;
	n0->Reduce();

	// copy to destination
	bool neg = ((num1.m_IsNeg && !num2.m_IsNeg) || (!num1.m_IsNeg && num2.m_IsNeg));
	if (n0inx >= 0)
	{
		if (neg)
			this->Neg(*n0);
		else
			this->Copy(*n0);
		FreeBigTemp(n0inx);
	}
	else
		if (neg) this->Neg();

	// delete sources
	FreeBigTemp(n1inx);
	FreeBigTemp(n2inx);
}

///////////////////////////////////////////////////////////////////////////////
// mul bignum with signed number, store result here

void bignum::Mul(const bignum& num1, bint num2)
{
	if (num2 < 0)
	{
		this->MulU(num1, -num2);
		this->Neg();
	}
	else
		this->MulU(num1, num2);
}

///////////////////////////////////////////////////////////////////////////////
// mul bignum with unsigned number, store result here

void bignum::MulU(const bignum& num1, buint num2)
{
	// special cases
	if (num1.Equ0() || (num2 == 0)) { this->Set0(); return; }
	if (num1.Equ1()) { this->SetU(num2); return; }
	if (num2 == 1) { this->Copy(num1); return; }
	if (num2 == 2) { this->Add(num1, num1); return; }
#if BIGBITS > 32
	if ((num2 & (num2-1)) == 0) { this->LShift(num1, Bits64(num2) - 1); return; }
#else
	if ((num2 & (num2-1)) == 0) { this->LShift(num1, Bits32(num2) - 1); return; }
#endif

	// limits
	bint dec = num1.m_DecNum;
	bint len = num1.m_IntNum;
	bint i = dec + len;

	// prepare destination number
	len++;
	int n0inx = -1;
	bignum* n0 = this;
	if ((len > m_IntMax) || (dec > m_DecMax))
	{
		n0inx = GetBigTemp();
		n0 = &BigTempNum[n0inx];
		n0->SetMaxSize(len*BIGSIZE, dec*BIGSIZE, false);
	}
	n0->m_DecNum = dec;
	n0->m_IntNum = len;

	// prepare 1st source
	int n1inx = -1;
	const bignum* n1 = &num1;
	if ((n1 == n0) || num1.m_IsNeg)
	{
		n1inx = GetBigTemp();
		bignum* n1b = &BigTempNum[n1inx];
		n1b->SetMaxSize((len-1)*BIGSIZE, dec*BIGSIZE, false);

		if (num1.m_IsNeg)
			n1b->Neg(num1);
		else
			n1b->Copy(num1);
		n1 = n1b;
	}

	// multiply
	buint carry = n0->MulStr(0, num2, n0->Base(-dec), n1->Base(-dec), i);

	// carry
	*n0->Base(len-1) = carry;

	// data reduction
	n0->m_IsNeg = false;
	n0->Reduce();

	// copy to destination
	bool neg = num1.m_IsNeg;
	if (n0inx >= 0)
	{
		if (neg)
			this->Neg(*n0);
		else
			this->Copy(*n0);
		FreeBigTemp(n0inx);
	}
	else
		if (neg) this->Neg();

	// delete sources
	FreeBigTemp(n1inx);
}

///////////////////////////////////////////////////////////////////////////////
// mul by signed number

void bignum::Mul(bint num)
{
	if (num < 0)
	{
		this->MulU(-num);
		this->Neg();
	}
	else
		this->MulU(num);
}

///////////////////////////////////////////////////////////////////////////////
// mul by unsigned number

void bignum::MulU(buint num)
{
	// special cases
	if (this->Equ0() || (num == 0)) { this->Set0(); return; }
	if (this->Equ1()) { this->SetU(num); return; }
	if (num == 1) return;
	if (num == 2) { this->Add(*this); return; }
#if BIGBITS > 32
	if ((num & (num-1)) == 0) { this->LShift(Bits64(num) - 1); return; }
#else
	if ((num & (num-1)) == 0) { this->LShift(Bits32(num) - 1); return; }
#endif

	// convert number to positive value
	bool neg = m_IsNeg;
	if (neg) this->Neg();

	// limits
	bint dec = m_DecNum;
	bint len = m_IntNum;
	bint i = dec + len;

	// multiply
	buint carry = this->MulStr(0, num, this->Base(-dec), this->Base(-dec), i);

	// carry
	if (m_IntNum < m_IntMax)
	{
		*this->Base(m_IntNum) = carry;
		m_IntNum++;
	}

	// data reduction
	this->Reduce();

	// restore signs
	if (neg) this->Neg();
}

///////////////////////////////////////////////////////////////////////////////
// factorial (values up to 10000! are cached to fast access)

void bignum::Fact()
{
	buint num = this->UIntVal();
	this->Fact(num);
}

void bignum::Fact(buint num)
{
	buint i = 2;
	this->Set1();

	// cache
#ifdef OPTIMISE
	if (num >= FACTSCALE)
	{
		i = num/FACTSCALE;
		if (i > FACTNUM) i = FACTNUM;
		FactCacheUpdate((int)i);
		this->Copy(FactCache[i-1]);
		i = i*FACTSCALE + 1;
	}
#endif // OPTIMISE

	// calculation
	for (; i <= num; i++)
	{
		this->MulU(i);
	}
}
