M
Matthew Moss
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
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 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
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.
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 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
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.