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

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?

## 1 comment:

Hi.I've just read your post about division algorithm.I really want to know what bigint construct you use in that code.Can you post it?

Many thanks!

@:Sorry for my bad english.

Post a Comment