180 Long Division

Description

Your task this week is to perform and display long division.

Your program should take two arguments: the dividend and the divisor. Your output should display the long division needed to determine the quotient and remainder (if it exists). For example, if I run your program like so:

$ ruby long_division.rb 11 4096

Your program’s output should be:

    372 R4
  +----
11|4096
   33
   --
    79
    77
    --
     26
     22
     --
      4

If there is no remainder, do not display anything after the quotient; that is, do not display R0. As an alternative to the remainder, you may instead calculate the decimal fraction out to N digits (e.g. use command-line option –digits=N or similar to switch to decimal fraction output).

Summary

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
      break
    end
  end
end

# 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 103 but less than 104). 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 line:

    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.


Wednesday, February 04, 2009