Thread: Division Algorithm

  1. #16
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by LuckY
    All I need to define is HugeFloat/HugeFloat.
    Then good luck!!
    But, does your HugeFloat class preserves infinite or even extreme precision?? If not, mabe 1/B could result in extremely small numbers, that way losing precision
    Last edited by xErath; 11-13-2004 at 11:17 PM.

  2. #17
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Thanks. I planned on defaulting division to a max of 40-50 decimal digits and providing an accessor for the user to change it if need be. But for the 1/denom division (before the *numerator) I will extend it out very far.

    Again, thanks for that extremely obvious, yet severely overlooked point.
    Last edited by LuckY; 11-14-2004 at 12:01 AM.

  3. #18
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Just visiting from:
    http://cboard.cprogramming.com/showthread.php?t=58598

    Thanks for the link Lucky, there're definitely things here that'll come in handy for me too.

    Though, you DO have a slight edge on me, seeing as you've already done all the other algorithms, how about the first one to divide:
    13548799798829387945373749837921371233849837951739 844835749734323512626549871545564165544165544.4654 75263446544562345646
    by
    98798797344524524351324655267598672321658395865987 12341164454524624142346523415232331522133245236455 45324579823475829785293452.130165409874

    wins?

    (And if anybody wants to do it on paper, that's fair game too)

    [EDIT]
    I sure did place two points, my bad
    [/EDIT]
    Last edited by Epo; 11-14-2004 at 11:55 AM.

  4. #19
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Hahaha. That's a good one... You're on.

  5. #20
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    I think it's Pi....

    Well then I best get cracking! Well...it's 3:00 in the morning, but when I wake up! Oh, you best watch out.

    *Tips his hat* Until next time folks.

  6. #21
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Here's what I use in my BigInt class. digits is a std::vector with digits 0-9.
    I use base 10 for easy output.
    Code:
    BigInt& BigInt::operator/=(const BigInt& denominator)
        {
            using namespace std;     
            
            //Single digit optimization
            if (denominator.digits.size() == 1)
            {
                int remainder;
                singleDivision( denominator.digits[0], remainder);
                return *this;
            }  
            
            if (denominator.isZero())
            {
                //Not correct, but we don't use exceptions here
                *this = 0;
                return *this;
            }
            
            //Is denominator larger?
            if (denominator > *this)
            {
                *this = 0;
                return *this;
            }
            
            //The result
            BigInt result;
            int rsize = digits.size()-denominator.digits.size()+1;
            result.digits.resize(rsize,0);
            
            for (int i=rsize-1;i>=0;--i)
            {
                //Guess the value for result[i]
                result[i] = 5;
    
                while (*this - result*denominator < 0)
                    result[i]--;
                
                while (*this - result*denominator >= 0)
                    result[i]++;
                
                result[i]--;
            }
            result.trim();
            
            if (denominator.negative)
                result.negative = !result.negative;
            if (negative)
                result.negative = !result.negative;  
            
            *this = result; 
            return *this;
        }
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #22
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Code:
    1354879979882938794537374983792137123384983795173
    98448357497343.23512626549871545564165544165544465
    475263446544562345646
    /9879879734452452435132465526759867232165839586598
    7123411644545246241423465234152323315221332452364
    5545324579823475829785293452.130165409874 = 
    1.371352704991228E-64
    You placed two points in the 1st number!! bah So with the point in the other place:
    Code:
    1354879979882938794537374983792137123384983795173
    984835749734323512626549871545564165544165544.4654
    75263446544562345646
    /9879879734452452435132465526759867232165839586598
    71234116445452462414234652341523233152213324523645
    545324579823475829785293452.130165409874 =
    1.371352704991228E-32
    Me wins!

  8. #23
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Wow, you didn't even give me time to wake up! Hehe

    Alright....so....that contest's over rather quickly.

    Good job though!

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    does your HugeFloat class preserves infinite or even extreme precision??
    It cant provide infinite precision, since no computer has enough memory to store the floating point result of 1/3 to an infinite precision.

    But for the 1/denom division (before the *numerator) I will extend it out very far.
    You'll only need may be two decimal places more than the given precision, I think.
    But I think that you'll have to weight the costs of performing multiplication after division of unity, it may be more than immediately doing the division.

    The current method that I'm implementing considers the fact that division by repeated subtraction of numbers which are comparable in size is relatively fast.
    So I use long division to break up the numerator into smaller chunks by which division by repeated subtraction is performed.
    In addition while using the c=a*b guess and check idea means that I'll have to make an additional subtraction to find the remainder of an intermediate step in the long division, with division by repeated subtraction I get this required remainder as a consequence, and so can use it immediately.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #25
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by laserlight
    It cant provide infinite precision, since no computer has enough memory to store the floating point result of 1/3 to an infinite precision.
    Of course, i had that memory limitation in mind.. i meant like keeping a max of about 30 or 40 decimal digits, or streching to what ever the number requires, being of course, limited by the available memory...

  11. #26
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    I love long division. It's amazing how hard it can be to take a simple operation like long division and put it into code.

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    It's amazing how hard it can be to take a simple operation like long division and put it into code.
    Surprisingly easy (at least without much optimisation), actually.
    Then again I've already written a number of other functions that simplify the process.
    Here's from
    std::string BigInt::div(std::string a, std::string b)
    Code:
        ...
        std::string ret;          //return value
        std::string work_portion; //portion of a currently worked on
        for (int i = 0; i < a.length(); i++) {
            //add next digit of a to work portion
            work_portion.append(1, a[i]);
            //apply integer division by repeated subtraction
            ret += divRS(work_portion, b); //work_portion = remainder
        }
        return trim(ret); //intermediate quotient = 0 => leading 0s
        ...
    Code:
    std::string BigInt::divRS(std::string& a, std::string b) {
        std::string count("0");
        while (cmp(a, b) >= 0) {
            a = sub(a, b);
            count = increment(count);
        }
        return count;
    }
    It does depend on divRS(), which in turn depends on cmp(), sub() and increment() (which depends in part on add() ), so yeah.
    The good part is that once I had div() done, getting mod() done for modulo was easy.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    That is a nice, sturdy solution. The only problem (as you eluded to) is that you have to perform the division digit-by-digit and with a several thousand digit division that can be slow. Of course if there is no better a solution that would be a great algorithm to fall back on.

    The solution I'm pondering is to multiply 1 by 10 until it is >= denominator then count the subtractions and include it in the quotient until we have achieved several digits (maybe 40) or there is nothing more to divide. Then we multiply that quotient with the true numerator and bam, there's your answer. A real problem that I foresee with doing this with floating point numbers is that it could leave endless trailing 9's instead of rounding up to 1 as it should...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Division Algorithm
    By author in forum C Programming
    Replies: 4
    Last Post: 04-15-2005, 12:02 PM
  2. Division Algorithm
    By -=neo=- in forum C++ Programming
    Replies: 2
    Last Post: 02-01-2005, 07:32 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM