Faster way to divide numbers

This is a discussion on Faster way to divide numbers within the C++ Programming forums, part of the General Programming Boards category; I'm working on overloading operators (still working on making a bignum decimal class) and I ran in to a snag. ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    416

    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;
            }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,272
    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)
    Last edited by brewbuck; 04-29-2009 at 12:47 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. divide 2 hex numbers
    By dust555 in forum C Programming
    Replies: 5
    Last Post: 04-16-2007, 12:20 AM
  2. Writing unique numbers to an array
    By yardy in forum C Programming
    Replies: 6
    Last Post: 12-27-2006, 09:15 PM
  3. pulling numbers from files....
    By Confuzz in forum C++ Programming
    Replies: 3
    Last Post: 09-07-2004, 08:49 PM
  4. Adding Line numbers in Word
    By Mister C in forum A Brief History of Cprogramming.com
    Replies: 24
    Last Post: 06-24-2004, 09:45 PM
  5. Need a way to divide a group of numbers
    By adrianxw in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 09-11-2003, 01:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21