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

A note on Rotational Commutativity

Topics: Orthogonal matrices, Commutativity, rotational commutativity

Requires: Basic Familiarity with Matrices (transposes, inverses, identities, ...)

   Notation:

Identity Matrix: I
Zero Matrix: 0
Matrix [multiplicative] Inverse of A: A^-1
Matrix Transpose of A: A^T
Matrix Both Inverse and Transpose applied to A: A^-T
  (Since the inverse of the transpose of a matrix equals the transpose of the inverse of the matrix.)

   Assumptions:

If we multiply matrices below, we assume that they are conformable.
If we we take the inverse of a matrix, we assume that the matrix has an inverse.

   Definitions:

If we multiply an expression on the left, we call this premultiplying by the matrix.
If we multiply an expression on the right, we call it post multiplying.
A matrix Q is orthogonal if, when it is multiplied by its transpose, the result is the identity.
Examples:
  Q^TQ = I
  QQ^T = I
Another way to say this is that, for an orthogonal matrix, its transpose is equal to its inverse.
  Q^T = Q^-1
And so it follows that
  Q = Q^-T

Preliminaries:

In my prior post, I talked about the fact that, in general, matrix multiplication doesn't commute. And I mentioned, in passing, that in some special cases do commute.
Some cases that do commute are:

    IA = AI = I        Identity commutes with anything.
    0A = A0 = 0        Zero commutes with anything.

Since matrices don't generally commute, one has to be careful to make it clear, when multiplying through by some matrix whether you are post multiplying. If your a multiplying by a matrix and don't state what kind you are doing, it is assumed you are premultiplying.

Rotational Commutativity:

I can't find a proper name in the literature that describes the property I discuss here. I'm calling it "Rotational Commutativity" for lack of a better term. If someone knows of a proper term for it in the mathematics literature, please drop me a line. Put "Matrices" in the subject line of the note.

You can see that I was able to exchange Q and Q^T in the definition of Orthogonal above.
You might be tempted to say that orthogonal matrices commute. This is not correct. Those only commuted because their product was I.

Lets make this clearer by considering a list of matrices that, when multiplied together, have a product of I.

Example: ABC = I
We can premultiply the equation by A^-1, removing the A at the start, and replacing the I on the right hand side with A^-1.
    BC = A^-1
We then post multiply both sides by A which puts it on the right of the left hand side of the equals and cancels the term on the right hand side.
    BCA = I
So what did we do? We rotated the list by one item.
This shows that for a list of matrices that have the product I, we can produce any rotation. For ABC, we can produce ABC, BCA, and CAB, and all are equal to the identity.
If we had only two matrices AB, and their product was I, rotating the list produces BA, which is the same as swapping them.

Aside: This only worked because the collection had the product I. If we started with anything else there, the two steps would have had some other product. In the ABC case, if the right hand side of the equation were D, we would have ended up with BC = A^-1DA, which is ABCA^-1 = D.

This shows that for a list of matrices that have the product I, we can produce any rotation. For ABC, we can produce ABC, BCA, and CAB, and all are equal to the identity.
If we had only two matrices AB, and their product was I, rotating the list produces BA, which is the same as swapping them.

However, this rotation does not mean that that collection is the identity in any other order.
For example, the technique used can not generate CBA, BAC, or ACB, because they are not a rotation of ABC.

Navigation:

previous post | next post