BigInt Division

Mohn suggested sharing some of the BigInt code. The most interesting method I wrote was for division. And it is highly in-efficient, but I feel interesting. The general long division learnt in Algebra class if implemented is more efficient.

Assume that the other BigInt operations like <, *, - etc have already been implemented. I'll try to add descriptive comments within the code. (something which I should make a practice!!)

We were asked to implement a BigInt containing upto 100 digits. So I used a vector for that and a bool for sign of the number.

Here goes...

BigInt BigInt::
operator/(const BigInt& rhs) {
//hard code for RHS == zero
BigInt* zeroBigInt = new BigInt(0);
if ( (*this) == (*zeroBigInt) ) {
return *zeroBigInt;
}
//create copies of both lhs and rhs without sign
//set the sign of the answer later
//from now, lhs and rhs are the positive values of the numbers
BigInt* tempThis = new BigInt(*this);
tempThis->sign = true;
BigInt* tempRhs = new BigInt(rhs);
tempRhs->sign = true;
//if lhs < rhs value return 0
if ( (*tempThis)<(*tempRhs) ) {
delete tempThis;
delete tempRhs;
return *zeroBigInt;
}
//int quotient = 0;
//int factor = 0;
BigInt* quotient = new BigInt(0);

//get number of digits of lhs and rhs
int tempThisSize = tempThis->bigInt->size();
int tempRhsSize = tempRhs->bigInt->size();

//the difference between the two sizes should be atleast 2 digits
//tempThisSize will be decremented in the loop
while ( (tempThisSize) > (tempRhsSize+1) ){
//get the greatest factor of ten which is 2 digits smaller than lhs
BigInt* factor = new BigInt(1);
BigInt* tenBigInt = new BigInt(10);
for (int i=0; i<(tempThisSize-tempRhsSize-1); i++){
(*factor) = (*factor) * (*tenBigInt);
}
//cout << "factor " << (*factor) << endl;
(*quotient) = (*quotient) + (*factor);

//factorTemp is a copy of factor
BigInt* factorTemp = new BigInt(*factor);

//now increment the quotient by factor
//assume that we obtained a factor of 100 earlier
//in this step quotient is incremented by values of 100
//as 200, 300, .. till the muliplication tempThis is just exceeded
while( (*tempThis) >= (*zeroBigInt) ) {
(*tempThis) = (*tempThis) - ( (*factorTemp) * (*tempRhs) );
(*quotient) = (*quotient) + (*factor);
//cout << quotient << " " << (*tempThis) << " " << (*factorTemp) << endl;
}
//as a factor just higher than required has been taken
//perform a rollback
(*tempThis) = (*tempThis) + ( (*factorTemp) * (*tempRhs) );
(*quotient) = (*quotient) - (*factor) - (*factor);
delete tenBigInt;
delete factor;
delete factorTemp;
//cout << (*quotient) << " " << (*tempThis) << " " << endl;
//keep reducing tempThisSize
//if the earlier factor was 1000, now 100 can be generated
//so approaching the correct value
tempThisSize--;
}

//cout << "finished factor part!!" << endl;
//now to division by simple subtraction
//in the worst case, we'll have perform subtraction 99 times
BigInt* oneBigInt = new BigInt(1);
while ( (*tempThis) >= (*zeroBigInt) ) {
(*tempThis) = (*tempThis) - (*tempRhs);
(*quotient) = (*quotient) + (*oneBigInt);
//cout << (*quotient) << endl;
}
(*quotient) = (*quotient) - (*oneBigInt);
delete oneBigInt;

//set the sign of the output number
if ( (this->sign)==(rhs.sign) ) {
quotient->sign = true;
} else {
quotient->sign = false;
}

//some housekeeping and return
delete zeroBigInt;
delete tempThis;
delete tempRhs;
return *quotient;
}

Could have obtained a better perf if I created all the temporary BigInt's on the stack. Any more pointers? Any different algo's?