Requires: The information in The prior article in this series.
Definition: x mod y (called x modulo y), is just the remainder if you do integer divide of x by y
Disclaimer: The presentation below is mine, the ideas are from the late LeRoy N. Eide.
In my prior post on dividing by "Just in Time" subtraction [JITS], I pointed out that it did something bizarre if you were dividing by nine, and the number was not a multiple of nine. In this column I'll cover what it really does. And two different ways to look at that result that can make proper use of it.
The basic problem:
Given 9x = 1332, JITS properly produces 148 for x. And it produces the obvious (and correct) answer for any multiple of 9. So... let's look at the case where the given number is NOT a multiple of nine. As an example we can take 9x = 1336.
10x - 9x = x, so we try the subtraction:
Borrows:
10x = ? ? ? ? ? 0
-9x = 1 3 3 6
======================
x = ? ? ? ? ? ?
And we try to proceed as before...
Borrows: -1
10x = ? ? ? ? 4 0
-9x = 1 3 3 6
======================
x = ? ? ? ? 0 4
Digit by digit...
Borrows: -1
10x = ? ? ? ? 4 0
-9x = 1 3 3 6
======================
x = ? ? ? ? 0 4
... until we get to:
Borrows: -1 -1
10x = ... 5 5 7 0 4 0
-9x = 1 3 3 6
==========================
x = ... 5 5 5 7 0 4
And off to (countable) infinity producing 5's to the left. When this is shown to most people, they object at this point that that is *** not *** the right answer, and it doesn't even look meaningful. And when LeRoy first showed this to me I had a similar reaction. We are used to numbers trailing off to infinity to the right, but not trailing off to the left. [Except for Mathematicians that deal with p-adic numbers, who have seen this before. But that is a topic for a much later time.]
Our normal integers are represented by a series that may run off to smaller powers of the base, but only a finite distance into larger powers. So 123 is really 1x102+2*101+3*100, but if there are infinite powers we don't have much experience. It is easier to not think about these, then to think about this sort of infinite series.
There are several ways of looking at this state of affairs. On is that there is something we can do to "fix" this to match our normal interpretation. The other (and LeRoy's favorite) is to take this as an unfamiliar representation with it's own "virtues".
We'll just show the result from here on, instead of showing the computation of every step.
First, lets look at some very simple cases of dividing some small integers by 9. (And I'll assume everyone is happy with zeros trailing off infinitely to the left.)
0/9 borrows: 10x = ... 0 0 0 0 -9x = 0 ===================== x = ... 0 0 0 0 1/9 borrows: -1 10x = ... 8 8 9 0 -9x = 1 ===================== x = ... 8 8 8 9 2/9 borrows: -1 10x = ... 7 7 8 0 -9x = 2 ===================== x = ... 7 7 7 8 3/9 borrows: -1 10x = ... 6 6 7 0 -9x = 3 ===================== x = ... 6 6 6 7 ... 8/9 borrows: -1 10x = ... 1 1 2 0 -9x = 8 ===================== x = ... 1 1 1 2 9/9 borrows: -1 10x = ... 0 0 1 0 -9x = 9 ===================== x = ... 1 10/9 borrows: -1 10x = ... 8 9 0 0 -9x = 1 0 ===================== x = ... 8 8 9 0
That mysterious digit running to infinity on the left (call it d), is nothing but the distance to the next multiple of 9, and 9-d is nothing but the remainder when our 9x number is divided by 9. So, for example, if we have 9x = 1, the number running off is 8, so the remainder is 9-8 = 1. Subtract the remainder from the 9x value, to get it to be a multiple of 9, and use JITS to divide that by 9. A picky and astute student may question why we don't just add the 8 in to the 9x value and use JITS. Well, that would, for 9x=19, give not x=2 with remainder 1, but x=1 with remainder, 10.
On the other hand
While the above is a perfectly good way to view the integer problem, and it reduces to our traditional view, there is another view that looks at it not as divisor and remainder, but as a representation of numbers divided by nine. For example, we can take the "fractions above, and add them.
Carrys: ... +1 +1 +1 +1 1/9 = ... 8 8 8 8 9 +8/9 = ... 1 1 1 1 2 ============================ 9/9 = ... 0 0 0 0 1And
Carrys: ... +1 +1 +1 +1 1/9 = ... 8 8 8 8 9 +1/9 = ... 8 8 8 8 9 ============================ 2/9 = ... 7 7 7 7 8...
LeRoy went on to develop a full theory of rational numbers based on this, and it used to exist out on the net, but like his site, my site, and copies in places like the UK, those sites have long since gone away. I have posted
a copy of those notes on the Pages section of my blog at https://eccentric-math.blogspot.com/p/jits-rational-representations-notes.html.
Prior Post
Coming attractions:Why was LeRoy actually doing this in balanced ternary rather than decimal anyway? What is balanced ternary? What has this got to do with a somewhat obscure early series of Russian computers no longer in use? And why did the US not legally exporting transistors lead to that series? That, and more can be found in my Balanced Ternary post
Navigation:
No comments:
Post a Comment