Division by "Just in Time" Subtraction II

(Last edited July 25th, 2023 by John Halleck - fix arithmetic error.) Topics:     Division by "Just in Time" subtraction II
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 1x10²+2*10¹+3*10⁰, 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  1

And

 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:

next post | previous post

Division by "Just in time" Subtraction I

Topics:     "Just in Time" subtraction. Last edit January 25, 2024: minor fixes -jh
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:

next post on this topic

next post | previous post