Requires: Basic Familiarity with Decimal Arithmetic
Background:
The presentation on this page is mine, but all the ideas are due to the late Leroy N. Eide.
He had a Master's degree in Mathematics (thesis topic fractional derivatives, before they became fashionable.) And he almost had a Linguistics Degree, short only the field work.
He loved to explore areas that were different, and different takes on familiar areas.
Division by "Just in Time" subtraction (the term was coined by Dylan Pocock), was a favorite of his, and he later fleshed it out to a full fledged theory of rational number representations. Since his web site vanished after his death, and there seems to be no place on the net that his notes exist. So, with his prior and public permission, I have a copy at: https://eccentric-math.blogspot.com/p/jits-rational-representations-notes.html
On with the show:
One day LeRoy came across the hall from his office to mine, and put an equation on the board something like:
9x = 1332
Mentioning that 1332 was an exact multiple of nine, he asked how I would solve it.
[This isn't strictly true, actually he was doing divides by two, in balanced ternary, but leaping into that immediately would be unfair to the general reader. -JH]
Since this is a relatively simple problem, and he was grinning, I assumed this was a trick question.
I told him I would divide both sides of the equation by nine. He laughed, and said that that would be more work than was needed. He said a simpler way to solve it was as to set it up as:
10x - 9x = x
I objected that this was true but not useful, since I didn't have x and I certainly didn't have a clue as to what 10x was.
He grinned, and said that I was mistaken. "You do know that 10x ends in a zero." This is true, but I didn't yet see how that helped at all. "Let me write down the subtraction problem..." and he wrote the problem down:
10x = ? ? ? 0 -9x = 1 3 3 2 =================== x = ? ? ? ?
"You have the last digit of 10x, and of 9x. You can do that column's subtraction, generating a borrow of 1."
"AND, you now know the last digit of x is 8, so you know the next to the last digit of 10x.
Borrows: -1 10x = ? ? 8 0 -9x = 1 3 3 2 ==================== x = ? ? ? 8
And you can now do this for the next column, and fill in a digit of 10x.
Borrows: -1 10x = ? 4 8 0 -9x = 1 3 3 2 ==================== x = ? ? 4 8
And again:
Borrows: -1 10x = 1 4 8 0 -9x = 1 3 3 2 ==================== x = 0 1 4 8
(And, of course, we can remove the leading zero of x = 0148 to make x = 148)
We've just done one (admittedly non standard) subtraction, and we have divided a multiple of nine by nine. Notice that we've computed the digits from right to left, instead of the left to right order that division the usual way the traditional method generates them.
You can also divide by 11 this way: 11x - 10x = x.
In fact, you can use this to divide by any power of the base (10 in this case) plus one, or the power minus one.
An obvious problem is that this divide by 9 (as described) only works if the number were a multiple of nine.[Attempt to divide a non-multiple of nine by this method by hand, the problem will be obvious.] But, it can be extended to divide any positive integer by 9 easily, at the expense of having to look at part of the problem in a new way.
But, these are topics for later posts. (Partly because it is too late to publish them earlier.)
Loose ends:
It is limiting to only divide multiples of nine by nine. The next post on "Just in time subtraction" extends this to dividing any non-negative integer by nine (or 11, or any power of the base plus or minus 1.)
Since I mentioned above that my original exposure to this was in balanced ternary, I wrote a balanced ternary post. Combining balanced ternary arithmetic and Just in Time Subtraction, gives you quick right to left division by, for example, 2, 4, 8, 10, 26, 28, ... with the critical values being 2 and 10, just what you need to convert balanced ternary to binary or decimal without traditional time consuming left to right divisions.
Navigation:
No comments:
Post a Comment