Thread: Division Algorithm

  1. #1
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856

    Division Algorithm

    Okay, hopefully some of you can help with some fresh algorithm ideas. I've written (rather, I'm in the process of writing) a class called HugeFloat. It acts very much like a built-in type, but allows you to have floating point numbers of unlimited length and performs mathematic operations very rapidly (factorial 1200 takes under a second).

    My problem: the last big operator I need to define is division. With the other three (+ - *) it is much simpler because I can break up the work into smaller pieces, multiplying or adding only small portions at a time. I can't seem to think of an algorithm that would allow me to perform division in a similar way. In case it isn't obvious, I need to do it this way because if, for example, you want to divide 39183791734971398713857183075182394723298739182375 9237829384792347923847.239879574758937845973457 by 98237443591875498179374583457980745089274598274509 8237459827458923745089273459873459.283759283759230 527385728375 it's clearly impossible to do it without somehow breaking up the job into manageable pieces.

    Any ideas?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    hehe, I'm on this same problem myself, though with integers, which is easier.
    Still resisting the urge to look at the source of GMP

    So far one idea I have (at least one that is applicable to floating point) is to observe that
    c = a / b => a = b * c

    Then test values of c that make the value of (b * c) approach the value of a, refining the value of c on each iteration, perhaps drawing on the same idea as linear interpolation (sign change on a - (b * c) indicates that we've crossed the actual value).
    Unfortunately, multiplication is likely to be slow, so even with a "binary search" type of algorithm to test, you're still going to have a slow division.

    The other idea is to observe that as multiplication is repeated addition, division can be seen as repeated subtraction (number of repetitions gives the answer).
    I'm not too sure how to implement this for floating point division though.
    Last edited by laserlight; 11-13-2004 at 01:01 AM.
    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

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Just a thought. Could you do division by subtraction for the integer portion and then do a final "normal" division for the non integer portion.

    Edit: Actually I thought about it some more and you can do the entire division using the subtraction method. Once you are done with the whole number portion you simply "shift" the decimal and continue on.
    Last edited by Thantos; 11-13-2004 at 01:44 AM.

  4. #4
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    I would do it like....
    Keep subtracting the denominator from the numerator until the result is under 0. How many times you did is the first part [not including the time it was under 0]. Now, add the denominator to the result. I'll call this X. Now do the same as above, but now I want you to say the denominator is the numerator, and X is the denominator.

    Keep repeating this until the result of the subtraction yields 0.

    Here's an example: Let's say we want to calculate 72 / 32.
    We will keep a running tally called R (for 'Result').

    1. 72 - 32 = 40; R = 1
    40 - 32 = 8; R = 2
    8 - 32 = -24; No change.
    So far, R == 2.

    2. 32 - 8 = 24; R1 = 1
    24 - 8 = 16; R1 = 2
    16 - 8 = 8; R1 = 3
    8 - 8 = 0; R1 = 4
    So, 8 goes into 32 4 times. This means that we should add 1/4 to R.
    R = 2.25
    Now let's try 97 / 16.

    1. 97 - 16 = 81; R = 1
    .
    .
    .
    1 - 16 = -15; R == 6
    So far, R == 6.

    2. 16 - 1 = 15; R1 = 1
    .
    .
    .
    1 - 1 = 0; R1=16
    So, R1 is 16. That means we must add 1 / 16 to R. We end up with R = 6.0625

    If you want a way to calculate the ending fraction (i.e. 1/16), then keep going.

    What we just did in step one was modulus. This essentially simplifies the fraction down for us.

    One method of doing this is brute force: start at one, and keep subtracting a set value until we get just past the correct answer when we multiply it with the divisor (in this case, 16). Then, add the step back, divide our step by 10 , and keep going. This would take quite some time, but it would work.

    I'd perosnally choose this method. The pro's are that it can calculate infinitely long numbers (albeit slowly), and that you can set a limit to the precision and know how many digits are accurate.

    The major con is that it can take quite some time.
    I cannot think of another algorithm right now; I'm not in math mode. If anyone has a better algorithm, I would love to hear it.

    EDIT: Yes, he could use normal division, but he wanted infinite precision. If you're calculating a division that won't fit into a double, then you're out of luck.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Actually I thought about it some more and you can do the entire division using the subtraction method. Once you are done with the whole number portion you simply "shift" the decimal and continue on.
    Yeah, I suppose that would be possible.
    Should have thought about that, my seniors' 'A' level Computing paper did have a coursework problem involving representation of floating point bignum with the help of 2 integer bignum.
    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

  6. #6
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    laserlight: thanks for the link. I've actually never heard of GMP. good luck on your project. I actually wrote a huge int class (HINT) a few years ago now (very poorly and slowly but it worked) and it served as a very good basis for what I'm doing now (although now I'm coming up with even better ideas and may have to start over again). With my HINT class the array was stored as an array of chars using one for each digit (very terrible I know but it was just for the learning experience and I wanted extending the base assignment). Now what I'm doing is using an array of unsigned chars but to represent the actual numeric value for up to two digits (and the leading 1 or 2 is used for flags and such). What I'm thinking now is that using base 256 numbers would be much faster and more efficient, but before I go back to the drawing board I want to think out all the details. How are you approaching it?

    I have actually given mere moments of serious thought to doing anything but division (subtraction, guessing, etc) but it would be absolutely out of the question. To see what I mean think about a very "simple" worst case scenario of something huge like 13849849709135027935092509273509235297501973059720 5902937509235 divided by 3, for example. Division by subtraction would take a _very_ long time. I tried just decrementing a random ~18 digit number to zero earlier and I had to ctrl-C it because it took too long (it was going on an hour at the very least before I gave up). The same goes for the guessing. I want the division to go as rapidly as I've gotten the multiplication to go.

    I appreciate the ideas very much, but unfortunately they won't do... Any other thoughts?

  7. #7
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    "To see what I mean think about a very "simple" worst case scenario of something huge like 13849849709135027935092509273509235297501973059720 5902937509235 divided by 3, for example. Division by subtraction would take a _very_ long time."

    Well, I'd first check to see if the divisor * 100000 is less than the number being divided. If it is, then I'd multiply what I'm dividing by by 100000 and when I increment the current number of runs where the subtraction is greater than 0, increment it by 100000. Then, once it's below 0, divide by 10, increment by 10000, etc.

  8. #8
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Once you are done with the whole number portion you simply "shift" the decimal and continue on.
    This is actually similar to my multiplication algorithm. I take the entire integer + decimal parts and essentially remove the decimal altogether, noting how many total decimal digits there were. Then I do the multiplication in small pieces and just split the result at the index equal to the total decimal digits value. (the same way one might normally calculate a multiplication of two floating point numbers)

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Division by subtraction would take a _very_ long time.
    It depends on the relative size of the operands.
    Dividing a large number by a small number using division by subtraction would take much longer than for large numbers of similiar magnitude.

    The method that I am considering now is to check the magnitude.
    If they are similiar, I apply division by subtraction.
    Otherwise, I the divide and conquer guess and check algorithm, though its use is actually within a method taught to me in primary school.
    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. #10
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Well, I'd first check to see if the divisor * 100000 is less than the number being divided. If it is, then I'd multiply what I'm dividing by by 100000 and when I increment the current number of runs where the subtraction is greater than 0, increment it by 100000.
    It's not that I think the idea is terrible. It's just that it is too unreliable and slow. I am hoping to come up with some solution that has a big-O of n or n*m instead of infinity. Looping possibly endlessly (absolute worst case) to keep multiplying (another big-O of n*m not to mention the resources it consumes) simply to compare is just feels too brute-force.

    That said, it is definitely an idea I'll keep in mind. There may just be potential in some aspect of it. Thanks for the contribution.

    Then, once it's below 0, divide by 10, increment by 10000, etc.
    You do see that this would cause my division to be recursive right? If I have a 20 digit denominator and I keep multiplying to get up to the numerator then divide my 20+ digits by 10, the 10 will be multiplied continuously until it reaches that 20+ digits at which point it will be divided by 10.
    Just thought that was worth pointing out.

  11. #11
    Registered User Kybo_Ren's Avatar
    Join Date
    Sep 2004
    Posts
    136
    "If I have a 20 digit denominator and I keep multiplying to get up to the numerator then divide my 20+ digits by 10, the 10 will be multiplied continuously until it reaches that 20+ digits at which point it will be divided by 10."
    But you will check to see if that multiplied by whatever is still less than the numerator.

    Perhaps I wasn't clear enough or I am not understanding you.

  12. #12
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317
    I am not sure this will help or not but if you have a 20 digit denomintor divided by 3 couldn't you just move the pointer and add digits to the end of the three keeping track of how many digitis (each one is a power of 10 of course) and then just subtract?

    2700000000/3

    2700000000-300000000 9 times so the answer is 900000000
    ignore the decmal point and just subract then put the answer that many places over?

    if it were 2700000000/ .3 then get rid of the decimal by moving it over to the right on both digits.

    27000000000/3; now count the places over to match up the 3 with the 27 and then

    270000000000-30000000000 do this 9 times then adjust for the decimal point so the
    answer woud be 9000000000 .

    if you were going the other way say .3/27000000000 then you would just move the decimal for the 3 keeping track of how many you move it over.
    30000000000-27000000000it goes 1 time with a remainder of =3000000000 it is repeating if you add a digit and subtract again it goes 1 time so your answer would be .0000000000011111...adjusting for the decimal again.
    not sure if that would work in all cases haven't tried it yet.
    [edit] never mind guess i should have refreshed the post same as already mentioned i guess.
    Last edited by manofsteel972; 11-13-2004 at 06:20 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  13. #13
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    manofsteel: thanks for the suggestion. This is exactly what I was contemplating originally and what I was going to do, however my problem is not really how to do the division with decimal digits, but how to do the division with numbers that cannot naturally be handled by a computer. Thus, the subtraction solution, which again I will keep in mind. I just wish there was a more direct way.

    I actually did implement a huge integer division in my old HINT class and I think I better seriously look into how I did that because I have no idea any more.

    One very interesting thing I discovered while experimenting with division that I didn't realize before (but is basic division) is that the sum of the quotient of the integer part and the decimal part over the same denominator yields the same answer. So 123.456/78 is equal to 123/78 + 456/78 (again a very simple, basic math identity). This is how I planned to handle the decimal division. Perhaps breaking up the numerator into even smaller pieces may be part of a good solution.

  14. #14
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Well, remeber that A/B Is A*(1/B).. So you only need to consider the numerator to be 1, then multiply. That should ease up a bit...
    But are you asking for HugeFloat/HugeFloat or HugeFloat/(float,double,long double) algorithm ??
    Last edited by xErath; 11-13-2004 at 04:59 PM.

  15. #15
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    That is really a very a excellent point. Thanks xErath. All I need to define is HugeFloat/HugeFloat. Dividing by any built-in type is a simple task and really the only reason I have a problem is because you can't naturally perform a division for any non-built-in types.

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