Reverse division and continued fractions

By David Cary, edited by Jukka Korpela

The character “\” and reverse division

These notes relate to the discussion of the reverse solidus (backslash) character “\” in my Character histories: notes on some Ascii code positions. That document contains the following paragraph, after mentioning that the reverse solidus was originally proposed as a “reverse division” operator:

The phrase "reverse division" is rarely used nowadays, and some of the uses seem to refer to a machine instruction for division (such as FDIVR) which simply has the argu­ments in an order which is reverse to the normal division instruction. The proposal mentioned above seems to have meant something quite different, since it referred to continued fractions, perhaps meaning that a continued fraction which can be presented as [a1,a2,…,an] in abbreviated mathematical notation would be written as a1\a2\…\an in some programming language(s). I haven’t been able to track down any such usage.

I have added the words “seems to have” after David Cary has commented on this issue and presented what appears as a good explanation to me. This little document summarizes the explanation and hopefully clears up the history as well as the relationship between reverse division and continued fractions.

For mathematical and programming background, consult e.g. the MathWorld article on Continued fraction.

Reverse division concepts vs. continued fractions

There are several related concepts involved: a machine instruction for division with its arguments in a reversed order; a programming language equivalent of such an instruction; a purely mathematical notation for it; and a continued fraction notation. The first three are related in an obvious way.

There is at least one programming language, Julia, that actually uses the reverse solidus for reverse division (called “inverse divide” in Julia). Some other languages have an equivalent operator with a different symbol.

Using reverse division to express continued fractions

In mathematical or programming notations that have no “reverse division” operator, to calculate an approximation to a continued fraction you would have to write lots of parentheses:
x = b1/( b2/( b3/( a3 + b4/a4 ) + a2 ) + a1 ) + a0
x = a0 + b1/( a1 + b2/( a2 + b3/( a3+b4/a4 ) ) ).
For example,
x = 1/( 1/( 1/( 2 + 1/2 ) + 2 ) + 2 ) + 1
(estimate square root of 2 = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, …]) and
x = t / ( 1 - t2 / ( 3 - t2 / ( 5 - t2 / ( 7 - t2 / 9 ) ) ) ) (estimate tangent of angle t in radians).

If there were a reverse division operator, such that
a / b ≡ b \ a
and that operator had the same level of precedence as addition, so addition and reverse division were evaluated from left to right, like so,
a + b \ c ≡ (a + b) \ c
then the source code would have many fewer parenthesis, perhaps something like this:
x = a4 \ 1 + a3 \ 1 + a2 \ 1 + a1 \ 1 + a0.
For example,
x = 2 \ 1 + 2 \ 1 + 2 \ 1 + 2 \ 1 + 1 ( estimate square root of 2).
x = 9 \ t2 - 7 \ t2 + 5 \ t2 - 3 \ t2 + 1 \ t (estimate tangent of t).

Example: Forth

The preceding discussion was about purely mathematical notations. In the Forth pro­gram­ming language and in the RPN notation (which can be used as input to some calculators, so it could be regarded as a programming language), this notation is actually used, though with different symbols and with postfix order:
2 INV 2 + INV 2 + INV 2 + INV 2 + INV 1 + ( estimate square root of 2)
t2 = t^2 (t to power 2)
9 t2 swap / 7 - t2 swap / 5 + t2 swap / 3 - t2 swap / 1 + t swap / (estimate tan(t) in rad)
We can see that that using \ rather than swap / would make the code a bit more compact. The INV operator can be thought of as “1 \”).

Impact on machine code

If we look at the machine-language level, we can see that this goes beyond merely making the source look more pretty. Continued fractions naturally lead to using the “reverse division” machine instruction.

On many machines, the result of an addition always goes in one particular location (let us call this R1, although every machine gives it a different name). When that addition is followed by a divide, the “normal” division takes the previous result (in R1) as the numerator, while the “reverse” division takes that previous result (in R1) as the denom­i­na­tor. When evaluating continued fractions, the intermediate result falls into R1. That result is needed as the denom­i­na­tor of the next step, so naturally the compiler uses the “reverse” division machine-language instruction (even when the high-level language doesn’t have a reverse divide). Without that machine-language instruction, the compiler would be forced to shuffle intermediate results back and forth to other temporary registers.

About this document

This document is based on a text that David Cary sent me by E-mail 2002-11-24. With his permission, I converted it, somewhat edited, into HTML format and uploaded it onto the Web. In another E-mail message he commented his text:

It’s mostly speculation, anyway. Since every floating-point processor I’ve ever seen has a “reverse division” instruction, I speculate that (1) reverse division is useful for some­thing, (2) whoever put reverse division into the ASCII set knew that reverse division was useful for something (at least for representing reverse division instructions, even if it was unclear exactly why those were so useful).

I know several other times where my friends and I were mystified at something, we made up some plausible-sounding stories to explain it, and later discovered that the true history was something completely different.