The Universe of Disco

Sun, 01 Oct 2023

The Wikipedia article on “Irish logarithm” presents this rather weird little algorithm, invented by Percy Ludgate. Suppose you want to multiply !!a!! and !!b!!, where both are single-digit numbers !!0≤a,b≤9!!.

Normally you would just look it up on a multiplication table, but please bear with me for a bit.

To use Ludgate's algorithm you need a different little table:

$$ \begin{array}{rl} T_1 = & \begin{array}{cccccccccc} \tiny\color{gray}{0} & \tiny\color{gray}{1} & \tiny\color{gray}{2} & \tiny\color{gray}{3} & \tiny\color{gray}{4} & \tiny\color{gray}{5} & \tiny\color{gray}{6} & \tiny\color{gray}{7} & \tiny\color{gray}{8} & \tiny\color{gray}{9} \\ 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 & 14 \\ \end{array} \end{array} $$

and a different bigger one:

$$ \begin{array}{rl} T_2 = & % \left( \begin{array}{rrrrrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, & 3, & 6, & 12, \\ {\tiny\color{gray}{10}} & 24, & 48, & 0, & 0, & 9, & 18, & 36, & 72, & 0, & 0, \\ {\tiny\color{gray}{20}} & 0, & 27, & 54, & 5, & 10, & 20, & 40, & 0, & 81, & 0, \\ {\tiny\color{gray}{30}} & 15, & 30, & 0, & 7, & 14, & 28, & 56, & 45, & 0, & 0, \\ {\tiny\color{gray}{40}} & 21, & 42, & 0, & 0, & 0, & 0, & 25, & 63, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 35, & 0, & 0, & 0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, & 0, & 0, & 49\hphantom{,} \end{array} % \right) \end{array} $$

I've formatted !!T_2!! in rows for easier reading, but it's really just a zero-indexed list of !!101!! numbers. So for example !!T_2(23)!! is !!5!!.

The tiny gray numbers in the margin are not part of the table, they are counting the elements so that it is easy to find element !!23!!.

Ludgate's algorithm is simply:

$$ ab = T_2(T_1(a) + T_1(b)) $$

Let's see an example. Say we want to multiply !!4×7!!. We first look up !!4!! and !!7!! in !!T_1!!, and get !!2!! and !!33!!, which we add, getting !!35!!. Then !!T_2(35)!! is !!28!!, which is the correct answer.

This isn't useful for paper-and-pencil calculation, because it only works for products up to !!9×9!!, and an ordinary multiplication table is easier to use and remember. But Ludgate invented this for use in a mechanical computing engine, for which it is much better-suited.

The table lookups are mechanically very easy. They are simple one-dimensional lookups: to find !!T_1(6)!! you just look at entry !!6!! in the !!T_1!! table, which can be implemented as a series of ten metal rods of different lengths, or something like that. Looking things up in a multiplication table is harder because it is two-dimensional.

The single addition in Ludgate's algorithm can also be performed mechanically: to add !!T_1(a)!! and !!T_1(b)!!, you have some thingy that slides up by !!T_1(a)!! units, and then by !!T_1(b)!! more, and then wherever it ends up is used to index into !!T_2!! to get the answer. The !!T_2!! table doesn't have to be calculated on the fly, it can be made up ahead of time, and machined from brass or something, and incorporated directly into the machine. (It's tempting to say “hardcoded”.)

The tables look a little uncouth at first but it is not hard to figure out what is going on. First off, !!T_1!! is the inverse of !!T_2!! in the sense that $$T_2(T_1(n)) = n\tag{$\color{darkgreen}{\spadesuit}$}$$

whenever !!n!! is in range — that is when !!0≤ n ≤ 9!!.

!!T_2!! is more complex. We must construct it so that

$$T_2(T_1(a) + T_1(b)) = ab.\tag{$\color{purple}{\clubsuit}$}$$

for all !!a!! and !!b!! of interest, which means that !!0\le a, b\le 9!!.

If you look over the table you should see that the entry !!n!! is often followed by !!2n!!. That is, !!T_2(i+1) = 2T_2(i)!!, at least some of the time. In fact, this is true in all the cases we care about, where !!2n = ab!! for some single digits !!a, b!!.

The second row could just as well have started with !!24, 48, 96, 192!!, but Ludgate doesn't need the !!96, 192!! entries, so he made them zero, which really means “I don't care”. This will be important later.

The algorithm says that if we want to compute !!2n!!, we should compute $$ \begin{align} 2n & = T_2(T_1(2) + T_1(n)) && \text{Because $\color{purple}{\clubsuit}$} \\ & = T_2(1 + T_1(n)) \\ & = 2T_2(T_1(n)) && \text{Because moving one space right doubles the value}\\ & = 2n && \text{Because $\color{darkgreen}{\spadesuit}$} \end{align} $$

when !!0≤n≤9!!.

I formatted !!T_2!! in rows of !!10!! because that makes it easy to look up examples like !!T_2(35) = 28!!, and because that's how Wikipedia did it. But this is very misleading, and not just because it makes !!T_2!! appear to be a !!10×10!! table when it's really a vector. !!T_2!! is actually more like a compressed version of a !!7×4×3×3!! table.

Let's reformat the table so that the rows have length !!7!! instead of !!10!!:

We have already seen that moving one column right usually multiplies the entry by !!2!!. Similarly, moving down by one row is seen to triple the !!T_2!! value — not always, but in all the cases of interest. Since the rows have length !!7!!, moving down one row from !!T_2(i)!! gets you to !!T_2(i+7)!!, and this is why !!T_1(3) = 7!!: to compute !!3n!!, one does:

$$ \begin{align} 3n & = T_2(T_1(3) + T_1(n)) && \text{Because $\color{purple}{\clubsuit}$} \\ & = T_2(7 + T_1(n)) \\ & = 3T_2(T_1(n)) && \text{Because moving down triples the value}\\ & = 3n && \text{Because $\color{darkgreen}{\spadesuit}$} \end{align} $$

Now here is where it gets clever. It would be straightforward easy to build !!T_2!! as a stack of !!5×7!! tables, with each layer in the stack having entries quintuple the layer above, like this:

This works, if we make !!T_1(5)!! the correct offset, which is !!7·5 = 35!!. But it wastes space, and the larger !!T_2!! is, the more complicated and expensive is the brass thingy that encodes it. The last six entries of the each layer in the stack are don't-cares, so we can just omit them:

And to compensate we make !!T_1(5) = 29!! instead of !!35!!: you now move down one layer in the stack by skipping !!29!! entries forward, instead of !!35!!.

The table is still missing all the multiples of !!7!!, but we can repeat the process. The previous version of !!T_2!! can now be thought of as a !!29×3!! table, and we can stack another !!29×3!! table below it, with all the entries in the new layer being !!7!! times the original one:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\tiny\color{gray}{58}} & 25, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{65}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{72}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{79}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{86}} & 0, \\ \\ \hline \\ {\tiny\color{gray}{87}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color{gray}{94}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{101}} & 63, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{108}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{115}} & 0, \\ \\ {\tiny\color{gray}{116}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{123}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{130}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{137}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{144}} & 0, \\ \\ {\tiny\color{gray}{145}} & 0, & 0, & 0, & 0, & 0, & 0, & \ldots \\ \\ \hline \\ {\tiny\color{gray}{174}} & 49\hphantom{,} \\ \end{array} $$

Each layer in the stack has !!29·3 = 87!! entries, so we could take !!T_1(7) = 87!! and it would work, but the last !!28!! entries in every layer are zero, so we can discard those and reduce the layers to !!59!! entries each.

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\tiny\color{gray}{58}} & 25, \\ \\ \hline \\ {\tiny\color{gray}{59}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color{gray}{66}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{73}} & 63, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{80}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{87}} & 0, \\ \\ {\tiny\color{gray}{88}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{95}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{102}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{109}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{116}} & 0, \\ \\ {\tiny\color{gray}{117}} & 0, \\ \\ \hline \\ {\tiny\color{gray}{118}} & 49\hphantom{,} \\ \end{array} $$

Doing this has reduced the layers from !!87!! to !!59!! elements each, but Ludgate has another trick up his sleeve. The last few numbers in the top layer are !!45, 25,!! and a lot of zeroes. If he could somehow finesse !!45!! and !!25!!, he could trim the top two layers all the way back to only 38 entries each:

We're now missing !!25!! and we need to put it back. Fortunately the place we want to put it is !!T_1(5) + T_1(5) = 29+29 = 58!!, and that slot contains a zero anyway. And similarly we want to put !!45!! at position !!14+29 = 43!!, also empty:

The arithmetic pattern is no longer as obvious, but property !!\color{purple}{\clubsuit}!! still holds.

We're not done yet! The table still has a lot of zeroes we can squeeze out. If we change !!T_1(5)!! from !!29!! to !!23!!, the !!5,10,20,40!! group will slide backward to just after the !!54!!, and the !!15, 30!! will move to the row below that.

We will also have to move the other multiples of !!5!!. The !!5!! itself moved back by six entries, and so did everything after that in the table, including the !!35!! (from position !!32+29!! to !!32+23!!) and the !!45!! (from position !!14+29!! to !!14+23!!) so those are still in the right places. Note that this means that !!7!! has moved from position !!38!! to position !!32!!, so we now have !!T_1(7) = 32!!.

But the !!25!! is giving us trouble. It needed to move back twice as far as the others, from !!29+29 = 58!! to !!23+23 = 46!!, and unfortunately it now collides with !!63!! which is currently at position !!7+7+32 = 46!!.

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & \color{purple}{5}, & \color{purple}{10}, & \color{purple}{20}, & \color{purple}{40}, & 0, \\ {\tiny\color{gray}{28}} & 81, & 0, & \color{purple}{15} & \color{purple}{30}, \\ \\ \hline \\ {\tiny\color{gray}{32}} & 7, & 14, & 28, & 56, & 0, & \color{darkgreen}{45}, & 0, \\ {\tiny\color{gray}{39}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{46}} & {63\atop\color{darkred}{¿25?}} & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{53}} & 0, & 0, & \color{darkgreen}{35}, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, \\ \\ \hline \\ {\tiny\color{gray}{64}} & 49\hphantom{,} \\ \end{array} $$

We need another tweak to fix !!25!!. !!7!! is currently at position !!32!!. We can't move !!7!! any farther back to the left without causing more collisions. But we can move it forward, and if we move it forward by one space, the !!63!! will move up one space also and the collision with !!25!! will be solved. So we insert a zero between !!30!! and !!7!!, which moves up !!7!! from position !!32!! to !!33!!:

All the other multiples of !!7!! moved up by one space, but not the non-multiples !!25!! and !!45!!. Also !!49!! had to move up by two, but that's no problem at all, since it was at the end of the table and has all the space it needs.

And now we are done! This is exactly Ludgate's table, which has the property that

$$T_2(p + 7q + 23r + 33s) = 2^p3^q5^r7^s$$

whenever !!2^p3^q5^r7^s = ab!! for some !!0≤a,b≤9!!. Moving right by one space multiplies the !!T_2!! entry by !!2!!, at least for the entries we care about. Moving right by seven spaces multiplies the entry by !!3!!. To multiply by !!5!! or !!7!! we move right by or !!23!! or by !!33!!, respectively.

These are exactly the values in the !!T_1!! table:

$$\begin{align} T_1(2) & = 1\\ T_1(3) & = 7\\ T_1(5) & = 23\\ T_1(7) & = 33 \end{align}$$

The rest of the !!T_1!! table can be obtained by remembering !!\color{darkgreen}{\spadesuit}!!, that !!T_2(T_1(n)) = n!!, so for example !!T_1(6) = 8!! because !!T_2(8) = 6!!. Or we can get !!T_1(6)!! by multiplication, using !!\color{purple}{\clubsuit}!!: multiplying by !!6!! is the same as multiplying by !!2!! and then by !!3!!, which means you move right by !!1!! and then by !!7!!, for a total of !!8!!. Here's !!T_1!! again for reference:

$$ \begin{array}{rl} T_1 = & \begin{array}{cccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 & 14 \\ \end{array} \end{array} $$

(Actually I left out a detail: !!T_1(0) = 50!!. Ludgate wants !!T_2(T_1(0) + T_1(b)) = 0!! for all !!b!!. So we need !!T_2(T_1(0) + k) = 0!! for each !!k!! in !!T_1!!. !!T_1(0) = 50!! is the smallest value that works. This is rather painful, because it means that the !!66!!-item table above is not sufficient. Ludgate has to extend !!T_2!! all the way out to !!101!! items in order to handle the seemingly trivial case of !!0\cdot 0 = T_2(50 + 50)!!. But the last 35 entries are all zeroes, so the the brass widget probably doesn't have to be too much more complicated.)

Wasn't that fun? A sort of mathematical engineering or a kind that has not been really useful for at least fifty years.

But actually that was not what I planned to write about! (Did you guess that was coming?) I thought I was going to write this bit as a brief introduction to something else, but the brief introduction turned out to be 2500 words and a dozen complicated tables.

We can only hope that part 2 is forthcoming. I promise nothing.

[ Update 20231002: Rather than the ad-hoc backtracking approach I described here, one can construct !!T_1!! and !!T_2!! in a simpler and more direct way. Shreevatsa R. explains. ]

[ Update 20231015: Part 2 has arrived! It discusses a different kind of all-integer logarithm called the “discrete” logarithm. ]

[ Update 20231020: I think this is a clearer explanation of the discrete logarithm. Shorter, anyway. ]

[Other articles in category /math] permanent link