
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                         Long number - division                            //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#include "..\include.h"

///////////////////////////////////////////////////////////////////////////////
// divide 2 numbers (this=num1/num2), store result here and remainder to 'rem'
// num1 = dividend, num2 = divisor, this = quotient, rem = remainder (do integer division or NULL=do decimal division)

void bignum::Div(const bignum& num1, const bignum& num2, bignum* rem /* = NULL */)
{
	// clear remainder
	if (rem != NULL) rem->Set0();

	// special cases
	if (num1.Equ0()) { this->Set0(); return; }
	if (num2.Equ0()) { this->Fill(); return; }
	if (num2.Equ1()) { this->Copy(num1); return; }
	if (num2.EquM1()) { this->Neg(num1); return; }
	if ((num2.m_DecNum == 0) && (num2.m_IntNum == 1))
	{
		buint n = *num2.Base();
		if (!num2.m_IsNeg)
		{
			this->DivU(n);
			return;
		}
		else
		{
			bint n2 = -(bint)n;
			if (n2 > 0)
			{
				this->DivU(n2);
				return;
			}
		}
	}

	// !!!!!!!!!!!!!!!!!!!

/*
	// limits of integer part
	bint len1 = num1.m_IntNum;
	bint len2 = num2.m_IntNum;
	bint len = len1;
	if (len < len2) len = len2;

	// limits of decimal part
	bint dec1 = num1.m_DecNum;
	bint dec2 = num2.m_DecNum;
	bint dec = dec1;
	if (dec < dec2) dec = 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);
	*/
}

///////////////////////////////////////////////////////////////////////////////
// div by unsigned number, returns remainder, only integer part

buint bignum::DivUInt(buint num)
{
	// special cases
	if (this->Equ0())
	{
		if (num == 0)
			this->Set1();
		else
			this->Set0();
		return 0;
	}
	if (num == 0) { this->Fill(); return 0; }
	if (num == 1) return 0;

	// sign
	bool sign = false;
	if (m_IsNeg)
	{
		sign = true;
		this->Neg();
	}

	// divide number
	m_DecNum = 0;
	buint carry = this->DivStr(0, num, this->Base(), this->Base(), m_IntNum);

	// reduce number
	this->Reduce();

	// sign correction
	if (sign) this->Neg();

	return carry;
}

///////////////////////////////////////////////////////////////////////////////
// div by unsigned number, returns remainder

buint bignum::DivU(buint num)
{
	// special cases
	if (this->Equ0()) { if (num == 0) this->Set1(); else this->Set0(); return 0; }
	if (num == 0) { this->Fill(); return 0; }
	if (num == 1) return 0;
#if BIGBITS > 32
	if ((num & (num-1)) == 0) { this->RShift(Bits64(num) - 1); return 0; }
#else
	if ((num & (num-1)) == 0) { this->RShift(Bits32(num) - 1); return 0; }
#endif

	// sign
	bool sign = false;
	if (m_IsNeg)
	{
		sign = true;
		this->Neg();
	}

	// divide number
	buint carry = this->DivStr(0, num, this->Base(-m_DecNum), this->Base(-m_DecNum), m_DecNum + m_IntNum);

	// expand decimal part
	m_DecNum += this->DivUExpStr(carry, num, this->Base(-m_DecNum), m_DecMax - m_DecNum);

	// reduce number
	this->Reduce();

	// sign correction
	if (sign) this->Neg();

	return carry;
}
