KEK

gistfile1.cpp

BigInt::QuRem BigInt::div(const BigInt & d) const
{
	if (d.isNull()) {
		throw BigIntDivideByZeroException();
	}
	if (this->isNull()) {
		return (QuRem)std::make_pair(0, 0);
	}
		
	auto R = this->abs(), B = d.abs();
	BigInt Q;

	if (R.compareAbs(B) != -1) {
		int bits_shift = SOI - BigIntUtility::_log2(B.data.back()) - 1;
		R <<= bits_shift;
		B <<= bits_shift;
		lui eldest_dig = B.data.back();

		auto k = R.dig(), l = B.dig();
		Q.data.resize(k - l + 1);
		R.data.reserve(k + 1);

		for (int i = k - l; i >= 0; --i) {
			R.data.resize(i + l + 1, 0);
			lui temp = ( ((lui)(R[i + l]) << SOI) | R[i + l - 1]) / eldest_dig;
			Q[i] = (bui)(temp > C_MAX_DIG ? C_MAX_DIG : temp);
			R.normalize();
			subAbs(R, Q[i] * B, i);
			while (R.isNeg())
			{
				subAbs(R, B, i);
				R.negate();
				--Q[i];
			}
		}
		R >>= bits_shift;
		R.data.shrink_to_fit();
		Q.sgn = 1;
	}

	if (sgn * d.sgn == -1) {
		Q.negate();
		--Q;
		subAbs(R, d);
		R.negate();
	}

	if (d.isNeg())
		R.negate();

	Q.normalize();
	R.normalize();
	return std::make_pair(Q, R);

}