Reverse-engineering the "Irish logarithm"

October 02, 2023

Source: MJD’s blog post on “The Irish logarithm” (cites Wikipedia: Irish logarithm).

Apparently, Percy Ludgate (1883–1922) was an Irish amateur (was “Boy Copyist” in 1901, and “Commercial Clerk (Corn Merchant)” in 1911, later accountant), who in 1909—unaware of the work of Charles Babbage (1791–1871) and his analytical engine—designed a similar general-purpose (Turing-complete) computing machine.

As part of this machine, he needed to implement multiplication of one-digit numbers, and it appears that a two-dimensional lookup in a $10 \times 10$ table was hard in his design for some reason, so he instead came up with an idea that requires only looking up one-dimensional arrays. (Like Babbage, and like several early computers like the IBM 650, he was working in decimal—a multiplication table in binary is much simpler!) This is exactly what logarithms (invented by Napier in 1614) do: to compute the product of two numbers $a$ and $b$,

First we look up $a$ and $b$ in a table of logarithms, to get their respective logarithms $\log a$ and $\log b$,
We add these logarithms, getting the value $\log a + \log b = \log (ab)$.
Then we look up this value in a table of anti-logarithms (for logarithms, we can reuse the same table, as it is sorted…) to get the value of the product $a \cdot b$.

Ludgate could do something similar (he had mechanisms for adding and looking up a one-dimensional table), except not use logarithms exactly, as they would require fractional values rather than integers (and integer arithmetic is simpler). To be sure, he could have integer values if he would only need to multiply, say, powers of $2$: he could use the table:

1 2 4 8 16 32 64
0 1 2 3  4  5  6

with which to multiply, say, $4 \times 8$, he could look up for $4$ and $8$ in the top row the corresponding values in the bottom row ($2$ and $3$ in this case), add them (obtaining $5$), and look up $5$ in the inverse table, getting the correct value $32$. This is basically logarithms to base $2$ (see this old Usenet post quoted by MJD) but $\log_{2}3$ is no longer an integer (for example), so this idea cannot be used…

Or can it?

Could we make it work, for some appropriate values in the “logarithm” and “anti-logarithm” tables (even if they are not true logarithms)? Let’s say the “logarithm” table is some $f$—the table would only need to contain values $f(0), f(1), \dots f(9)$ as those are the only ones we will look up, though we could imagine the function $f$ having a larger domain. The “anti-logarithm” table would be basically the inverse of $f$ (say $g$), containing values for all products of two one-digit numbers, from $0$ to $81$. These should satisfy the property that $$a \times b = g(f(a) + f(b))$$or, assuming that $g$ is basically the inverse of $f$ (defined on a larger domain as mentioned), that simply $$f(a \times b) = f(a) + f(b)$$ for any $a, b$ in $[1 .. 9]$ (we’ll think about $0$ separately later).

What can we say about such an $f$?

In the first place, as multiplying by $1$ does not change the value—we need $f(a \times 1) = f(a) + f(1)$—we are forced to set $f(1) = 0$.
Let’s say we set $f(2) = c$ for some $c$. This forces some values: $f(4) = 2c$ and $f(8) = 3c$, and (conceptually, though we don’t need it in the table) $f(16) = 4c$ and $f(32) = 5c$ and $f(64) = 6c$.
Next if $f(3) = d$, this forces not only $f(9) = 2d$ and $f(27) = 3d$ and $f(81) = 4d$, but also things like $f(6) = c + d$ and $f(72) = 3c + 2d$. Basically this determines the values of $f$ at all values that are the product of two one-digit numbers, and have only $2$ and $3$ as prime factors.
By similar reasoning, picking the values $f(5)$ and $f(7)$ completely determine the values of $f$ on all integers of interest (one-digit numbers, and products of any two of them).

Can we pick arbitrary values for $(f(2), f(3), f(5), f(7))$, though? No! Suppose we picked $c = f(2) = 1$ (as earlier) and $d = f(3) = 5$ (say). Then we have a “collision” between the values of $f(32)$ and $f(3)$, which would prevent the whole thing from working—we would end up getting the same value for $f(8) + f(4)$ and $f(3) + f(1)$. So, after having picked a value for $f(2)$ which determines values for powers of $2$, we must pick a value for $f(3)$ such that none of the newly determined values collide with any of the previously determined values.

In particular, suppose we pick the value $f(2) = 1$, giving the following partial table:

1 2 4 8 16 32 64
0 1 2 3  4  5  6

In Python:

f = {1: 0}
g = {0: 1}
for i in range(1, 6): 
  f[2 ** i] = i
  g[i] = 2 ** i

Then after this, picking the value of $f(3)$ determines the values at: $3, 6, 9, 12, 18, 24, 27, 36, 48, 54, 72, 81$. The smallest value that remains “free” to be assigned as $f(3)$ is $7$, and (as $7$ is greater than all the values in the table) setting $f(3) = 7$ doesn’t cause any collisions. We now have the following partial table:

1 2 3 4 6 8  9 12 16 18 24 27 32 36 48 54 64 72 81
0 1 7 2 8 3 14  9  4 15 10 21  5 16 11 22  6 17 28

which will work for multiplying together any two one-digit numbers other than $5$ and $7$. Note that we’re relying on the fact that we’ll only ever multiply one-digit numbers: the coincidences like $f(48) + 4(32) = 11 + 5 = 16 = f(36)$ don’t matter to us, as we’re not going to use this table to multiply $48$ and $32$.

In Python (append to the earlier code):

f[3] = 7
for a in [3, 6, 9]:
    for b in [1, 2, 3, 4, 6, 8, 9]:
        f[a * b] = f[a] + f[b]
        g[f[a] + f[b]] = a * b

More interesting is the choice of $f(5) = x$: along with with the earlier choices, this determines values at $5, 10, 15, 20, 25, 30, 40, 45, 50$, as, respectively $x, x + 1, x + 7, x + 2, 2x, x + 8, x + 3, x + 14, 2x + 1$, and the smallest value of $x$ that works (for which all the earlier values are unoccupied) is $x = 23$.

In Python, for verifying:

x = 0
while True:
  x += 1
  if all(v not in f.values() for v in [x, x+1, x+7, x+2, 2*x, x+8, x+3, x+14, 2*x+1]):
     print(x)
     break

(This exercise reminds me of the “packed trie” idea, mentioned in F. M. Liang’s thesis—see page 15—and used by Knuth in TeX and in his program for Bentley’s word-counting problem… more on that some other time, but it’s a very similar idea of having arrays with “holes”, which can be “moved around” or “shifted” with the constraint that their values only fall in the “holes” of other arrays, and never collide.)

Once $f(5) = 23$ is chosen, we have a longer table:

f[5] = 23
for a in [5]:
    for b in [1, 2, 3, 4, 5, 6, 8, 9]:
        f[a * b] = f[a] + f[b]
        g[f[a] + f[b]] = a * b
        print(f'{a * b} -> {f[a*b]}')

i.e. the following values are added:

 5 10 15 20 25 30 40 45
23 24 30 25 46 31 26 37

Finally, $f(7)$ remains to be chosen:

x = 0
while True:
    x += 1
    if all(x + f[b] not in f.values() for b in [1, 2, 3, 4, 5, 6, 8, 9]) and 2*x not in f.values():
        print(x)
        break

This gives $f(7) = 33$, and now the table is basically complete:

f[7] = 33
for a in [7]:
    for b in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
        f[a * b] = f[a] + f[b]
        g[f[a] + f[b]] = a * b
        print(f'{a * b} -> {f[a*b]}')

i.e. the following values are added:

 7 14 21 28 35 42 49 56 63
33 34 40 35 56 41 66 36 47

There’s one final wrinkle: what if one of the two numbers we want to multiply is $0$? We’d want the result to be $0$ again. This means we need to pick a value for $f(0)$ too; the smallest value that works:

x = 0
while True:
    x += 1
    if all(x + f[b] not in f.values() for b in range(1, 10)) and 2*x not in f.values():
        print(x)
        break

turns out to be the nice round number $f(0) = 50$. This gives some more values in the table:

f[0] = 50
for a in [0]:
    for b in range(10):
        # f[a * b] = f[a] + f[b]
        g[f[a] + f[b]] = a * b
        print(f'{a * b} -> {f[a] + f[b]}')

or rather, tells us that the inverse table should contain $g(y) = 0$ for $y = 100, 50, 51, 57, 52, 73, 58, 83, 53, 64$.

So with all this, we have the following “forward” table:

for x in range(10):
    print(x, f[x])

Output:

and the following “inverse” table:

for x in sorted(g.keys()):
	print(x, g[x])

Output:

These are the two tables that were computed by Ludgate, and used as one-dimensional arrays (and are reproduced on Wikipedia).

Edit: Quick follow-up post on doing slightly better.