Thread: Faster way to divide numbers

I'm working on overloading operators (still working on making a bignum decimal class) and I ran in to a snag. I can do all the normal arithmetic, but dividing seems to escape me. I came up with the idea that a/b = c where c is the number I want, and instead I said a = b*c and lets loops through all the possible combinations of c*b until it equals a. Although this works, it's so inefficient I can't divide numbers with 5 or more decimal places since it's on the order of O(10^n) (10 numbers for each decimal place, n = number of decimal places). I would like some ideas on how to do this, if more than one decimal place can be accomplished at a time that would be awesome, but if not it wouldn't be any worse than my other operators. Here is my code for the dividing operator as it is now.

Code:

//the function bdouble.check(bdouble) checks if the passed argument is the same
//value as the one that is calling the function

        friend bdouble operator / (const bdouble a, const bdouble b)
        {
            bdouble<MAXSIZE> ret(0,0,0);
            bdouble<MAXSIZE> mult_b = b;
            
            //find 1/b to multiply by a
            do{
                ++ret;
                mult_b = b * ret;
                    
            }while(!mult_b.check(a));
            
            return ret;
        }

I did it the same way you do long division by hand, except in base 2. When doing it in base 2 the usual steps involving a multiply by the quotient and a subtract, and then a multiply by 10 and addition of the next digit instead turn into bit shifts or bit sets and the code comes out really simple.
You could check on the one on my homepage under useful classes.
I was just thinking of trying out an even more efficient method today though actually.

I was also thinking of changing it to base 2 for that purpose. It cuts out a lot of arithmetic. I looked at your bigint class to see how you went about solving it and noticed your bit shifts. I might go about it the same type of way. Out of curiousity, how efficient is your bigint class at multiplying and dividing. I found a way to cut out a lot of unneeded arithmetic from my multiplying function which cut off a few seconds, but it still takes upwards of 20 seconds to find the product out to 50,000 decimal places. Addition and subtraction on the other hand take less than a tenth of a second to the same precision.

Provided you already implemented multiplication, you can divide to an arbitrary number of digits of precision like this (written recursively and generally)

Code:

real divide( real numer, real denom, int ndigits )
{
    real result = 0.0;
    while( numer >= denom )
    {
        result += 1.0;
        numer -= denom;
    }
    if( ndigit > 0 && numer != 0.0 )
        return += 0.1 * divide( 10 * numer, denom, ndigits - 1 );
    return result;
}

The use of 0.1 and 10 is arbitrary -- they simply have to be inverses of each other. It implies that the base used for ndigits is 10. You could use some other value, depending on your internal representation of the bignum. If you represent it in binary, a base of 2 is more natural, and these would reduce to single bit shifts (and ndigits would be expressed in bits instead of decimal digits)