[SUMMARY] Long Division (#180)

Discussion in 'Ruby' started by Matthew Moss, Oct 26, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    Apologies for the delay with this quiz's summary. Here ya go.

    Long division is sometimes called _long division with remainders_ and
    is done repeatedly dividing the divisor into each digit of the
    dividend combined with the remainder of the previous division step.
    For our example, 11 divided into 4096, the steps are:

    1. Divide 11 into the first digit, 4; the result (i.e. first
    digit of the quotient) is 0 with remainder 4.
    2. Divide 11 into 40 (i.e. the previous remainder with the next
    digit of the dividend); result is 3 with remainder 7.
    3. Divide 11 into 79 (i.e. previous remainder 7 with next digit
    9); result is 7 with remainder 2.
    4. Divide 11 into 26; result is 2 with remainder 4.

    And so our quotient is 0372, usually written without leading zeros as
    372, with a remainder of 4.

    In Ruby, it is trivial to get the end result without all the
    intermediate steps:

    quotient, remainder = dividend.divmod(divisor)

    But this skips all the visible work that I wanted to see with this
    quiz. Basically, your code really has to go through all the
    intermediate steps in order to display them. With that in mind, let's
    look at the solution from _Ken Bloom_ whose solution, while not
    perfect, nicely separates the division logic from the display.

    Here is Ken's main loop:

    while dividend >= divisor
    Math.log10(dividend).ceil.downto(0) do |exp|
    magnitude = 10 ** exp
    trydiv, rest = dividend.divmod(magnitude)
    if trydiv >= divisor
    exps << exp
    dividends[-1] = trydiv
    quotient_digit, remainder = trydiv.divmod(divisor)
    products << quotient_digit * divisor
    quotient += quotient_digit * magnitude
    dividend = (remainder * magnitude + rest)
    dividends << remainder

    # display output

    [quotient, dividend]

    First, the outer loop exits once the dividend (updated during the
    loop) becomes less than the divisor. At that point, what dividend
    remains is the final remainder, and is returned to the caller along
    with the quotient, as can be seen in the final line of the function,
    `[quotient, dividend]`. This nicely follows the same convention as
    `divmod` mentioned above.

    The next loop takes the base-10 logarithm of the dividend, rounded up.
    For 4096, this is 4 (because 4096 is more than 10**3 but less than
    10**4). Essentially, this gives us the number of digits in the
    dividend and the upper limit of digits in the quotient, and with the
    next line:

    magnitude = 10 ** exp

    calculates successive, decreasing orders of magnitude to break down
    the dividend. For example, first time through the inner loop, `exp` is
    4, and `magnitude` is 10,000. That is used in the next line:

    trydiv, rest = dividend.divmod(magnitude)

    Although, in this example, the first time through the loop, `trydiv`
    will be zero and `rest` will be 4096, the second time through (when
    `exp` is 3 and `magnitude` is 1,000), `trydiv` becomes 4 and `rest`
    becomes 96. It should be seen and understood by this that 4096 can be
    composed of 4 * 1000 + 96. What Ken is accomplishing by all this is to
    pull of the most significant digit of the dividend each time through
    the loop: first is 4, then comes 0, then 9 and finally will be 6.

    The condition that follows, `if trydiv >= divisor`, checks to see
    whether the current digit for the quotient (at the current magnitude)
    is something other than zero. If so, that digit is determined in the

    quotient_digit, remainder = trydiv.divmod(divisor)

    For our example, we won't hit this line until `exp` is 2, when will
    make `trydiv` will be 40 and `rest` will be 96. At this point,
    `trydiv` is greater than `divisor`, and so the followup division gives
    us `quotient_digit` as 3 and `remainder` as 7. (Note: 3 * 11 + 7 == 40.)

    The next important part of handling the division is updating the
    dividend, done in this line:

    dividend = (remainder * magnitude + rest)

    Continuing with the example, when `exp` is 2, `dividend` becomes 796
    (i.e., 7 * 100 + 96). We can check the work by noting that the
    quotient digit, 3, times the divisor and current magnitude (100) is
    3300, and 3300 + 796 is our original dividend, 4096.

    So, what are the other lines in the loop? Basically, Ken keeps a
    record of the exponents, remainders, and dividends calculated during
    the process, so these can be used in the output section to display the
    long division.

    If you have time, take a good look at _Sebastian Hungerecker_'s
    solution. Not only does it handle the long division output, but can
    calulate the decimal (instead of a remainder), even repeating, and do
    division in a specified number base. Pretty sweet.
    Matthew Moss, Oct 26, 2008
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. George Marsaglia

    Assigning unsigned long to unsigned long long

    George Marsaglia, Jul 8, 2003, in forum: C Programming
    Eric Sosman
    Jul 8, 2003
  2. Daniel Rudy

    unsigned long long int to long double

    Daniel Rudy, Sep 19, 2005, in forum: C Programming
    Peter Shaggy Haywood
    Sep 20, 2005
  3. Replies:
    Feb 9, 2007
  4. Mathieu Dutour

    long long and long

    Mathieu Dutour, Jul 17, 2007, in forum: C Programming
    Jul 24, 2007
  5. Matthew Moss

    [QUIZ] Long Division (#180)

    Matthew Moss, Oct 17, 2008, in forum: Ruby
    Matthew Moss
    Oct 24, 2008

Share This Page