Thursday, February 25, 2010

Long division taken apart, continued

Now that we have taken long division apart, in the last posting, and made a multiplication table for the divisor `21`, in the posting before that, we are ready to look at the standard long division algorithm, with Jakow Trachtenberg's trick.

We are dividing `1543` by `21`, using the multiplication table

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42),(3,63),(4,84),(5,105),(6,126),(7,147),(8,168),(9,189)]`.

Start by writing

`\qquad\qquad\qquad\qquad\quad"****."`
`\qquad\qquad\qquad 21 )\bar1543.`

From the table, see that no whole `21`s go into `1` or into `15`, but that `7` whole `21`s, but not `8`, go into `154` :

`\qquad\qquad\qquad\qquad\qquad\quad7"*."`
`\qquad\qquad\qquad 21 )\bar1543.`
`\qquad\qquad\qquad\qquad\quad147 .`

Subtract `1470` from `1543` leaving `73`.

`\qquad\qquad\qquad\qquad\qquad\quad7"*."`
`\qquad\qquad\qquad 21 )\bar1543.`
`\qquad\qquad\qquad\qquad\quad\ul1470.`
`\qquad\qquad\qquad\qquad\qquad\quad73.`

From the table, again, `3` whole `21`s, i.e. `63`, go into `73`, leaving `10`.

`\qquad\qquad\qquad\qquad\qquad\quad73.`
`\qquad\qquad\qquad 21 )\bar1543.`
`\qquad\qquad\qquad\qquad\quad\ul1470`
`\qquad\qquad\qquad\qquad\qquad\quad73.`
`\qquad\qquad\qquad\qquad\qquad\quad\ul63.`
`\qquad\qquad\qquad\qquad\qquad\quad10.`

This is the stopping point for divmod division, so that `1543 :- 21 = 73 " remainder " 10.`

For decimal division, one continues `21`s into `100` go `4` times, i.e. `84` leaving `16`.

`\qquad\qquad\qquad\qquad\qquad\quad73.`
`\qquad\qquad\qquad 21 )\bar1543.`
`\qquad\qquad\qquad\qquad\quad\ul1470`
`\qquad\qquad\qquad\qquad\qquad\quad73.`
`\qquad\qquad\qquad\qquad\qquad\quad\ul63.`
`\qquad\qquad\qquad\qquad\qquad\quad10.0`
`\qquad\qquad\qquad\qquad\qquad\qquad\ul8.4`
`\qquad\qquad\qquad\qquad\qquad\qquad1.6`

This continues until one has reached the desired degree of accuracy.

Long division taken apart

When we divide, we are trying to find out how many times the divisor (e.g. 21) goes into the dividend (e.g. 1543).

We could just repeatedly subtract, keeping a tally of the number of times we have subtracted, stopping when further subtraction would give a negative result.  At least, that is how we could do divmod division.

Keeping such a tally would be tedious, however.  It is better to subtract large but convenient multiples of the divisor, than smaller multiples, keeping tally of these separately as we go.

In our usual decimal system of numeration, powers of ten are particularly convenient multipliers.

In 1543, the highest nonzero column is the thousands column.  We can therefore try subtracting thousands of `21`s.  We could not subtract `21` thousand even once from `1` thousand and anything without the result being negative.  So we need `0` thousands of `21`s, and we still have `1` thousand and something.

Next, we try hundreds of `21`s.  Again, we cannot subtract even `21` hundreds even once from `15` hundred and something, without the result being negative.  So we need `0` hundreds of `21`s, and we still have `15` hundred and something.

Next, we try tens of `21`s.  We can subtract `21` tens from `154` tens and something.  Indeed, we can subtract `7` times, a total of `147` tens, without getting negative result.  So now we have that `154` tens and `3` is the same as `7` lots of `21` tens, and then `7` tens and `3`.

Next we try whole `21`s.  We can subtract `21` from `73` just `3` times without going negative.  This subtracts a total of `63` from `73`, leaving `10`.

So now we have that `1543` is the same as `7` lots of `21` tens, and `3` lots of `21` ones, and a further `10`.

This can instead be understood as `70` lots of `21`, and `3` lots of `21`, and `10` more.  This in turn is `73 xx 21` and `10`.  i.e.

`\qquad\qquad\qquad 1543 = (73 xx 21) + 10.`

If we are doing divmod division, we can stop :

`\qquad\qquad\qquad 1543 -: 21 = 73" remainder "10.`

But if, instead of a remainder, we want the quotient to have a fractional part expressed as a decimal, then we keep going.

We have `10` that still needs to be divided by `21`.  So now we try subtracting tenths of `21`.  `10` is `100` tenths.  We can subtract `4` lots of tenths of `21`, i.e. `84` tenths, from `100` tenths, leaving `16` tenths.

Next, we try subtracting hundredths of `21` from `160` hundredths.  `7` hundredths of `21` is `147` hundredths, which when subtracted from `160` hundredths leaves `13` hundredths.

Stopping at this point, we find that

`\qquad\qquad\qquad 1543 = (73.47 xx 21) + 0.13`,

which we can write

`\qquad\qquad\qquad 1543 -: 21 = 73.47" remainder "0.13`.

The preceding discussion has been rather lengthy--such work is usually set out in a much more compressed format.  Unfortunately, long division seems to have been taught procedurally without adequate preparation, so that the elided computational form entrains elided thinking.  Even among the few in these calculator-infested days who can still actually do long division, a substantial fraction can give no convincing account of why the standard long division algorithm works.

Building ad hoc multiplication tables

Proportion tables are sometimes useful for doing long division. 

For many people, the most difficult part of that standard long division algorithm is estimating which multiple of the divisor to subtract.  Jakow Trachtenberg taught a simple trick for avoiding this difficulty.

In the next posting, we are going to divide 1543 by 21, using the standard long division algorithm and Trachtenberg's trick.

The first step is to invest some time making a table of multiples of `21`, up to the `9 xx 21`.  The `0` and `1` rows are obvious :

`\qquad\qquad\qquad[(0, 0),(1, 21)]`.

The `2` row can be found by doubling the second row :

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42)]`.

The `3` row can be found by adding the `1` row and the `2` row :

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42),(3,63)]`.

The `4` row can be found either by adding the `1` row to the `3` row, or else by doubling the `2` row.  One picks whichever is more convenient :

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42),(3,63),(4,84)]`.

The `5` row can be found either by adding the `2` row and the `3` row, or else by adding the `1` row and the `5` row.  Again, one picks whichever is more convenient :

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42),(3,63),(4,84),(5,105)]`.

One continues in this way, constructing the next row opportunistically, until at last one has :

`\qquad\qquad\qquad[(0, 0),(1, 21),(2,42),(3,63),(4,84),(5,105),(6,126),(7,147),(8,168),(9,189)]`.

This can be checked by casting out nines, if one knows how to do that.  (If not, it needs to be the subject of yet another post.)

Now we are ready divide anything by `21`.

`\qquad\qquad\qquad[(0, 0,(0)),(1, 21,(3)),(2,42,(6)),(3,63,(0)),(4,84,(3)),(5,105,(6)),(6,126,(0)),(7,147,(3)),(8,168,(6)),(9,189,(0))]`.

This checks out, so we can rely on the table we have made.