Overloaded division operator for HugeInt [duplicate]

Question

Possible Duplicate:
Division with really big numbers

I need to overload the / operator to work on two HugeInt objects which are defined simply as an array of 30 shorts. This is homework, btw, but I have been wracking my brain for days on this problem.

I have overloaded the * operator already:

HugeInt HugeInt::operator*(const HugeInt &op2){
HugeInt temp;
short placeProducts[hugeIntSize + 1][hugeIntSize] = {0};
short product;
int carry = 0;
int k, leftSize, rightSize, numOfSumRows;

leftSize = getDigitLength();
rightSize = op2.getDigitLength();

if(leftSize <= rightSize) {

    numOfSumRows = leftSize;

    for(int i = (hugeIntSize - 1), k = 0; k < numOfSumRows; i--, k++) {

        for(int j = (hugeIntSize - 1); j >= k; j--) {

            product = integer[i] * op2.integer[j] + carry;

            if (product > 9) {

                carry = product / 10;

                product %= 10;

            } else {

                carry = 0;
            }
            placeProducts[k][j - k] = product;
        }
    }

} else {
    numOfSumRows = rightSize;

    for(int i = (hugeIntSize - 1), k = 0; k < numOfSumRows; i--, k++) {

        for(int j = (hugeIntSize - 1); j >= k; j--) {

            product = integer[j] * op2.integer[i] + carry;

            if (product > 9) {

                carry = product / 10;

                product %= 10;

            } else {

                carry = 0;
            }
            placeProducts[k][j - k] = product;
        }
    }
}
sumProductsArray(placeProducts, numOfSumRows);

for(int i = 0; i < hugeIntSize; i++)
{
    temp.integer[i] = placeProducts[hugeIntSize][i];
}

return temp;}

But how do I overload the / op? My main problem isn't with the C++ code or syntax, but with my algorithm to divide. When I multiply I am able to do it digit by digit. I store each product (aka 1's digit of bottom times every digit above, then 10's digit time every num above using my carry algorithm) in my 2d array. Every time I get new product it is offset to the left by n + 1, which "multiplies" it by the required power of 10. Then I just sum up all the columns.

I can't for the life of me figure out how to code the long division method. Since I'm dealing with two arrays it has to be digit by digit, and I suspect it might be as easy as reversing the multiplication algorithm. Nested loops and subtraction? I would need a variable for the quotient and reminder? Is there a better method? I just need to be pointed in the right direction.

Answer 1

In computational division of integers, there are a few interesting results:

• numerator < denominator implies quotient = 0
• numerator == denominator implies quotient = 1
• numerator > denominator, long division would be needed to determine quotient.

The first two conditions can be satisfied with a for loop. You could overload the less-than and equals relational operator to encapsulate this behavior.

For the long division, you will need your multiplication operator as well as overloaded less-than and subtraction operators, and an append digit member function to perform the operation.

It's brute force, but should get the job done.