The Power of Three and the Wooden Computer

The mystery of one of the almost-forgotten pioneers of the computer starts Phil Factor on a quest to explore and simulate in SQL the arithmetic operations of the lost wooden computer of Thomas Fowler. It is a homage to a little-known genius and an illustration of some curious SQL techniques.

Perhaps the prettiest number system of all is the balanced ternary notation, which consists of radix-3 representation using –1, 0, and +1 as “trits” (ternary digits) instead of 0, 1, and 2.
Donald Knuth Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition

This article is about an exploration of an old, little known, and very curious part of the history of computing and my attempts to understand it better, using SQL. It concerns an ordinary working man, a provincial town clerk doing repetitive calculations, who in 1840 not only discovered a clever way of representing numbers for mechanical calculation, but went on to devise a working calculating machine built out of wood. In some ways, his ‘balanced ternary’ system is superior to our own, as Donald Knuth once observed. It may seem oddly irrelevant to you, and it certainly looked that way to me for a while, yet it ended up by giving me plenty of insights into contemporary IT problems, and it turned into a fascinating puzzle.

The quest for Thomas Fowler

In the Bodleian library, there is the last copy of what is, at first glance, a very strange and puzzling publication, printed in 1838. It is a book of numbers with their binary and ternary equivalent, published at a time when there was no obvious use for binary or ternary numbers at all, no digital computers, nothing. Binary or ternary maths wasn’t part of Victorian culture. Even Babbage was, at that time, using decimal arithmetic for the difference engine. On the face of it, it wouldn’t be that much stranger if we discovered a two-hundred-year-old oil painting of a lady talking into a smartphone.

Why did Thomas Fowler publish it? Fortunately, the book has been scanned by Google for you to inspect. He explains why.

THE following TABLES are Published chiefly for the purpose of facilitating the very troublesome Calculations, which occur every Quarter in making up the Accounts of POOR LAW UNIONS. Having myself been employed in the Torrington Union, to make up the Accounts, at the commencement, I found those Calculations the most troublesome part of the business, and had recourse to the common Logarithms, which certainly abridged the labour, yet even with this valuable aid I was not satisfied, and was constantly searching after some other method more simple, and of easier application;—happily, I hit on the Idea, that any Number might be produced, by a combination of the Powers of the Numbers 2 or 3, and consequently, that the same Indices of the Powers that produced any two or more Numbers, would also represent any other two or more quantities bearing the Ratios of these Numbers, one to another respectively.”

Fowler had never been taught anything about binary or ternary number systems. No books at that time had any information about this. His most significant contribution to computer science was his explanation of the balanced ternary system, which is so elegant and easy to do repetitive calculations that it was well worth the extra bother of translation from decimal to ternary. In fact, he seems to have been the first to discover the practical value of the balanced ternary number system, and certainly the first to exploit it. Essentially, he had discovered that any number could be represented in as a series of values that could be -1, +1 or 0 and represented a power of three according to its ordinal position in a string. Fowler was doing his calculations in this ‘balanced ternary notation’ because it saved him a great deal of time as a council employee doing repetitive calculations, as he explains in his booklet. He had discovered that you could calculate what we’d call ‘percentages’ by simple addition or subtraction of various pre-calculated landmark percentages if you translated the decimal figures into balanced ternary. In fact, once you’d done this conversion, you could then do any repetitive division, multiplication, calculation of a proportion or percentage on them, purely by simple addition; doing the calculation once for every power of three in the range, and subsequently just doing simple addition based on the ternary representation of each number you need to do the calculation for. He explains all this in his booklet.

A simple example of usage

Imagine that goods had a tax rate of 22% (VAT in the UK is currently 20% which is easy to calculate in your head)

We make ourselves a simple calculator that has to change only when the rate changes

Now, if we want to calculate the figure of 22% of a sum like, for example, 341234, and we have no modern calculator to do it in an instance, we turn 341234 into its balanced ternary equivalent, using Mr Fowler’s splendid booklet to get …

Having done that, we get out our pencil and paper and add up the relevant values from the third column of the chart according to the sign in that position. (A trit is a single position in a ternary number, represented by either a -,+ or 0.)

The answer is 75071.5, which we achieved with nothing but simple addition. I’ve attached a simple spreadsheet to allow you to try it out and see what is going on under the covers. Why would Mr Fowler have been so excited by this? Because ‘mental’ addition –without a calculator- is much easier, quicker, and less error-prone than multiplication and division. It meant he got home on time. This idea was a real practical benefit to him in his work.

Thomas Fowler and the Power of Three

Thomas Fowler of Torrington, in North Devon, Britain, was a man of his time, in an age where everything seemed possible. He was born in 1777. Despite his lack of education or qualifications, he was able to argue on equal terms with Airey, Babbage and De Morgan, the leading mathematicians of the day. Like Michael Faraday, Richard Trevithick, or George Stevenson, he had little formal education. Like them, it didn’t stop either his confidence or energy, and it didn’t stop his peers respecting his abilities. He was a habitual inventor, who had already discovered and patented the principle of the thermosiphon that lead to the introduction of water-based central heating.

Such was Thomas Fowler’s obvious resourcefulness that he established himself as the local printer, council officer, and bank manager in his home town. His father had been a cooper, a very skilled craft, and Thomas had also had a good basic education before being apprenticed to a fellmonger. He was a skilled woodworker and had a fascination for mathematics. He soon became relatively prosperous by taking over the local printworks, and transforming it into a modern concern, supplemented with printing machinery he’d designed and built himself.

In his book, funded by a local squire who was impressed by his ingenuity, he finishes his description of his accounting calculations with a tantalizing demonstration of balanced ternary multiplication:

“I may now conclude, with an Example of Multiplication, by the Ternary Scale, which scarcely requires any mental exertion whatever; no Multiplication, nor even Addition, is required, as ordinarily practised.”

I have to admit that I had plenty of ‘mental exertion’ trying to understand it, at first. It becomes a bit clearer if we lay it out in the same way that we do multiplication by hand.

Once again, he avoids any multiplication in favour of simple addition, but I’ll explain more of the nuts and bolts of this later on in this article, and show how the ‘carry’ is performed.

He finishes the introduction to the book with the teasing sentences

“In the course of my observations on the Binary and Ternary Scales, I have fallen on a species of Binary and Ternary Arithmetic, which appears to possess some curious Properties, but, as writing on this subject is incompatible with my present purpose, I have only given a short Example of Multiplication, in what may be termed, Ternary Arithmetic, the process is extremely easy, and may be extended to very large Numbers.

Should the Sale of the present Edition be favourable, another will soon follow, in which the Ternary Table will appear under another Form, and extend from Unity to Numbers almost indefinitely great, and also contain some other curious and I hope, useful matter.”

Before we get too immersed in what Thomas Fowler had discovered, I need to explain a bit more about the balanced ternary system and how its remarkable properties led him to design and build a wooden calculating machine.

The example of multiplication has the puzzling line: +-+00-0 = 564.

That left-side value is in balanced ternary, a system based on the curious properties of ‘the power of three’. Anyone who used the old-fashioned weighing scales would be familiar with ‘Bachet’s problem of weights‘; the way that any weight of, say, between one and forty ounces could be done with just four weights: a 1-ounce weight, a 3-ounce weight, a 9-ounce weight and a 27-ounce weight. You chose one or more weight, just putting them on one scale or the other, while the item being weighed was on one of the scales.

With four ‘trits’ of the value 27, 9, 3 and 1, you can represent any value between -40 and +40 by either subtracting them (-), adding them (+) or not using them (0). Negative numbers are as natural to represent as positive ones.

  -40 = ----
  -39 = ---0
  -38 = ---+
  -37 = --0-
  -36 = --00
  -35 = --0+
  -34 = --+-
  -33 = --+0
  -32 = --++
  -31 = -0--
  -30 = -0-0
  -29 = -0-+
  -28 = -00-
  -27 = -000
  -26 = -00+
  -25 = -0+-
  -24 = -0+0
  -23 = -0++
  -22 = -+--
  -21 = -+-0
  -20 = -+-+
  -19 = -+0-
  -18 = -+00
  -17 = -+0+
  -16 = -++-
  -15 = -++0
  -14 = -+++
  -13 = ---
  -12 = --0
  -11 = --+
  -10 = -0-
   -9 = -00
  -8 = -0+
  -7 = -+-
  -6 = -+0
  -5 = -++
  -4 = --
  -3 = -0
  -2 = -+
  -1 = -
   0 = 0
   1 = +
   2 = +-
   3 = +0
   4 = ++
   5 = +--
   6 = +-0
   7 = +-+
   8 = +0-
   9 = +00
  10 = +0+
  11 = ++-
  12 = ++0
  13 = +++
  14 = +---
  15 = +--0
  16 = +--+
  17 = +-0-
  18 = +-00
  19 = +-0+
  20 = +-+-
  21 = +-+0
  22 = +-++
  23 = +0--
  24 = +0-0
  25 = +0-+
  26 = +00-
  27 = +000
  28 = +00+
  29 = +0+-
  30 = +0+0
  31 = +0++
  32 = ++--
  33 = ++-0
  34 = ++-+
  35 = ++0-
  36 = ++00
  37 = ++0+
  38 = +++-
  39 = +++0
  40 = ++++

So, -40 equals ‘—-‘, because it is -27-9-3-1. Similarly, -8 is ‘-0+’ because it is -9+0+1. In Bachet’s weights system, the ‘-‘ means ‘put the weight on the same scale as the thing being weighed’ and ‘+’ means ‘put the weight on the other side to the thing being weighed’ and ‘0’ means ‘leave the weight in the box’.

Why is this exciting? It is because it solves a fundamental problem of the binary system, which is that binary number have to be stored in a fixed width so that we can represent negative numbers. This is why there is such a rich and confusing plethora of numeric data types in SQL Server or .NET. I once had to write a Binary-coded decimal (BCD) math package in 8080 Assembler. It is accurate, but it isn’t elegant. I’d have done anything short of murder for a simpler way of coding numbers like this. To represent negative numbers in binary we must use Two’s Complement, which assumes a fixed length of representation. In the way that we use numbers in the real world, they just aren’t fixed length; and many of our woes with overflow and rounding errors are due to this simple problem. The ternary system doesn’t have this problem, as it is tri-state. This would have been a godsend. It can be extended to support the ternary equivalent of the decimal point. You can use it for floating point numbers too. With the balanced ternary number, there would be no need for separate encoding for decimal, integer and floating-point numbers. It is more like handling strings. Of course, to be effective you would need a processor that codes in ternary in its registers and has all the math primitives, such as addition and multiplication. These can be, and have been, made. Basically, in a database or the application you could have a single number format for every numeric datatype.

Given all this, why the lack of contemporary interest in ternary computing? It could have turned out rather differently.

The Wooden Ternary Computer

Fowler’s book alone is enough to secure his place in the history of computing, but there was much more behind his interest in the Ternary system than he was revealing. What Fowler didn’t explain in his book, although there were some tantalizing hints, was that he was already engaged in designing and building a wooden, mechanical computing machine in his back-garden workshop, based on the balanced ternary system.

He spent the final part of his life working on this wooden computer, his most ambitious project. He envisaged a small precision metal instrument but hadn’t the machinery or skills to do it, so he set to work to build a mock-up out of wood to demonstrate the principles. It was the size of a weaving loom, and similar in appearance.

Like everything else he did, he threw all his mental energy into trying to improve it. When it was finally revealed in 1840, the design of the mechanical computer deeply impressed Babbage, as well as Baily and De Morgan, who all described it in some detail. Papers about the computer were read to the Royal Society, and it was exhibited for some years in the 1840s, in the George III Museum of Kings College, London, alongside Babbage’s Difference Engine.

Fowler wrote “This Machine was constructed entirely with my own hands (principally in Wood) with the utmost regard to economy and merely to put my Ideas of this mode of calculation into some form of Action; It is about 6 feet long , One foot deep and three feet wide., In Brass & Iron it might be constructed so as not to occupy a space much large than a good portable writing desk and with powers such as I have described.”

Sadly, the creation of two successive designs for the ternary calculating machine were Fowler’s final work: he died in late middle age, dictating to his daughter a description of the machine on his deathbed. Happily, we still have this description of the device and the way it worked. There is a representation of it in a stained glass window in Torrington Church.

Sadly, without Fowler’s advocacy, the machine attracted little interest, for a variety of reasons. Perhaps the main one was that Babbage’s difference engine could print, and the primary requirement was to print tables for calculating inclination for ranging guns, for navigation and for logarithmic tables. The available tables were inaccurate due to human error, and there was an urgent need for something better. There was no demand then for a calculating machine. Also, the wooden calculator required that the numbers were converted to and from ternary. It was a considerable culture-shock and had to be done by lookup, or by a rather laborious addition/subtraction process described by Fowler in his book. Fowler was trying to demonstrate the principles of the system rather than a practical device and the audience could only see the wood.

It was another half century before Burroughs produced the first commercially-successful calculator. In the meantime, industrial society adapted to the need for computational skills. People discovered that if they spent a large part of their working lives adding up figures, or doing engineering calculations, they became very quick and accurate at it. As recently as forty years ago, I witnessed accountants consistently checking a column of figures on an A4 sheet of paper in around three seconds with complete accuracy. If one includes the OCR input, that feat was impossible to perform with the computing devices that were around at the time. Mechanical and electronic calculators took a long time to get broad acceptance because of the huge potential of the brain for training. Just study, for example, what a professional musician can do!

Since Fowler’s pioneering work, there has been relatively little interest in the ternary system. However, the first working ternary computer was built in Russia, at the Moscow State University, in 1958, designed by Nikolai P. Brusentow and his colleagues. They named it Setun, after the river that flows near the university campus. From 1958 to 1965 around fifty of them were built. The aim was to create a small, simple and cheap computer, that could be used in schools and offices. The design performed well and Setun-70 (1970), a two-stack computer, followed. Had it been given the funding by the state that it deserved, this type of computer would rival the supremacy of the binary system. Although it would be possible to map balanced ternary numbers to binary storage by using two bits per trit, you can’t process ternary numbers quickly in any of the current binary CPUs because it really needs three-state logic to implement mathematic operations. Flip, Flap, flop rather than Flip Flop, as Donald Knuth observed.

Following Fowler’s death, his wooden computer was eventually put into storage, having been broken into several pieces to make it fit the space. The remains were returned to the family. They were unable to reassemble it and, at some point, it disappeared. We now know of its appearance only through an illustration that is part of a memorial stained-glass window in Torrington Church. We have no detailed plans, only Fowler’s description and De Morgan’s account. Recently, a group of historians of computing lead by Mark Glusker have been able to reconstruct parts of the mechanism from the contemporary accounts and the illustration.

After a century and a half of neglect, we are beginning to realize the full significance and relevance of what Fowler discovered.

Exploring the balanced ternary system in SQL

The most interesting thing about Fowler’s contribution to computer science was the balanced ternary system. Basically, it is both a storage and representational system of numbers, decimal, floating-point and integer, that lends itself intrinsically to calculation and manipulation. So, let’s explore this system, using SQL. It could be any other language but many implementations have been done already. Besides, SQL tables have a strange affinity with the table in Fowler’s book. We are not doing this with even the remotest thought that it is a practical idea, but because it is a great way to understand, test, and appreciate the system. I admit to enjoying myself. It exercised some SQL muscles that were getting a bit flabby.

Anything that involves simply converting balanced ternary numbers to integers and doing math on that is cheating. It is too easy. I’m more interested in working out what Fowler had in mind for his vision of mechanical calculation and how he might done this in detail, at the low level; and how we might do it in the future with tri-state logic. We don’t know exactly how he performed addition, subtraction, multiplication and division with the wooden calculating machine, though Mark Glusker (reference at the end) has made a convincing reconstruction of part of the machine. It is intriguing to model the possible ways of doing it. The code for these following SQL routines is attached to the article.

Creating a Number Table

The first exercise for a SQL implementation is to have a ‘number table’ that has both decimal integers and their ternary equivalents, for lookup. This is the approach that Fowler took with his booklet, though it was necessarily in a truncated form for publication.

We also want to convince ourselves that no number has two different balanced ternary representations, and vice-versa. We want a quick reference for testing routines and understanding the way the system works.

As there are only three possible values for each digit, you can easily get all the combinations and permutations of ‘-‘,’+’ and ‘0’ by simply doing repeated cross joins on them, and then calculating the integer. For a broader number table of greater range, you just add cross-joins. Of course, if you have, say, a nine-digit range, zero will be nine zeros long where just one suffices, and so on. It would be nice to truncate leading zeros. Also, we will need to convert from balanced ternary to integer.

For a few of the subsequent routines, I use a lookup view of the actual positional values of the trits of a ternary number. Here is a view that does this. 

From Balanced Ternary to Integer

The classic approach to this is to use iteration. This can be translated to SQL Server but we are more likely to choose a set-based method for performance. However, it is always useful for double-checking

An inline table-valued function will always do better

So, it is plain sailing to go from ternary to integer.

Removing leading zeros

For certain operations, we will also want to remove leading zeros. Here, we need to ensure that if there are only zeros, then one zero is left. Here again, an inline function is the way to go.

Part of the script is a quick assertion test to ensure that it works

So now, with these two table-valued functions in place, we can then create our lookup table.

Creating a lookup table for conversion

We’ll restrict ourselves to a tryte of nine trits wide, giving us 59049 integers between 29524 and -29524. A register of 27 trits wide would be enough for most of us, and would represent 7625597484987 numbers, about the same as a 44-bit word, but you’ll need a faster computer and more patience than I have, to calculate them all.

We now have a quick way of translating between integer and balanced ternary. We can easily test things out. We can now progress to the simple mathematical operations that so engrossed Thomas Fowler. The table that we produced in the preceding introductory paragraph was produced simply by the query …

… and we now have an excellent testbed to checking mathematical operations.

Just one last task before we do so, to have a routine that converts from integer to Balanced ternary.

Converting From Integer to Balanced Ternary

And now, with an assertion test, we can check that it works with the whole range!

The Basic Mathematical Operations

The next step is to check out negation, addition, incrementing, multiplication and division. This starts easy, but doesn’t stay easy.

Negation

To turn a positive BT (balanced Ternary) number into its negative or vice versa, all you need to turn all the ‘+’ symbols into ‘-‘, and all the ‘-‘ symbols into ‘+’. You leave ‘0’s well alone.

I do this:

Giving

I’d be pleased if there is a more efficient way!

You can, of course, now prove to yourself that this works by reading them in the lookup table …

… which gives …

 

Abs

With the ABS function, you are just negating a negative number and leaving a positive one. A positive number starts with a + and a negative one starts with a ‘-‘, just like decimal notation. The precise meaning is different, though. Here is a simple example.

Increment and Decrement

Incrementing is the same action as decrementing, and is a subset of full binary addition so I’ll deal with it here. Binary increments can quite often lead to cascading flips of the more significant bits. Ternary increments are less prone to this, so you gain performance from treating it as a separate operation. I’ll use a recursive approach. using the simple rules for this operation, SQL Server functions don’t really handle defaults well, hence the need for the DEFAULT keyword.

Binary Addition

Binary addition refers to simple addition of two values, an L_value and an R_value. We will need more than this for multiplication, which is the ability to sum an arbitrary set of values.

Here is a simple addition just to show how it is done.

Starting from the least significant right-hand side, we look at the digit in the two values. Two zeros result in a zero, of course. In the next column is a minus and a zero, leaving a minus. All is simple until we get to the fifth column with two minuses. Hmm. There is a ‘minus’ carry and a ‘plus’ residual. That means that the next column should end up with zero, but there is a carry and so it is a minus. Then it is all simple until we get to the final left-side column where the two plusses give a ‘minus’ carry and a ‘plus’ residual. The carry appears in the rightmost column of the sum.

Knuth summarizes all this in his table:

Which I’ve translated

By ‘Carry’ I mean the number carried over from the summation of the previous trigit.. The ‘carry’ for addition is unusual in that it can be positive or negative. We are dealing with both positive and negative numbers. The ‘carried’ row is the value that must be carried to the next column because of the calculation

Subtraction is the same operation as addition. You just add a negation of the number. It is just a simple string manipulation. Carry is just a simple single-character ternary value, and so it can be dealt with simply. The obvious approach is iterative but we like to avoid that.

You can use Knuth’s lookup table to do the addition, and I rather like it because it is closer to the spirit of Fowler’s wooden computer.

The other approach I use is more complicated than strictly necessary as it deals with any amount of values of carry, which is necessary for the Sum_BT function. However, it isn’t much simpler to use Knuth’s lookup table. We are, however, rather cheating in that we are using integer division and a modulus function

So we can test the validity of these by a little test harness that will run from SSMS.

This makes use of our table of ternary values against their integer values to make sure that all give the same answer.

Yes, it looks as if ternary addition works OK!

Sum Addition

We need to be able to do addition of a whole collection of ternary numbers if we are to have the necessary tools for multiplication. This turns out to be only slightly more complicated than addition. We just need to create a user table type that allows us to pass a read-only table to a function.

So now we can create a function that will sum any quantity of ternary numbers that we wish

Now that we have this, we need to test it to make sure it works.

Multiplication

We can now return to that tantalizing example of multiplication, of which Thomas Fowler said, “scarcely requires any mental exertion whatever; no Multiplication, nor even Addition, is required, as ordinarily practiced.”

It makes more sense to those of us who learned long division at school if one adds in the ‘0’s that Fowler left out.

If the relevant trit of the multiplier is ‘+’, then the equivalent partial product is the multiplicand shifted left by the place. If it is ‘-‘, then it is the negated multiplicand similarly shifted. The ‘0’ does nothing. Then the partial products are summed to get the result. All very easy.

And now we can check that it works

Conclusion

Did Thomas Fowler invent something without precedent? Yes, he combined the principles of mechanical calculation with the simplicity of the ternary system to create a successful calculating machine. Had Fowler been given the resources lavished on Babbage, and Babbage’s robust health, he could well have gone on to make the same breakthroughs that Babbage made, such as printing the output and programming the calculations.

Is there still something we can learn from this? We have gone so far down the track of binary technology that is hard to see a ternary computer like the Setun providing anything more than we can get from binary technology. However, there is, potentially, gains to be made in creating maths packages that use balanced ternary, at least in their storage form, because these would hold out the promise of providing a single number type without the dangers of overflow.

For me, though, the biggest excitement is to explore the world of a stubborn, intelligent and determined man born over two hundred years ago in relatively humble circumstances, educating himself by night by thumbing through textbooks to the light of a candle, and then blazing a pioneering trail in a number of different technologies, fueled by a passion for technology, anger and sheer obstinacy. I would love to see him take up his place in the history of computing alongside the better-known pioneers of information technology. He deserves it.

References

Glossary

  • Ternary Scale – the number system based on trits, equivalent to the decimal system.
  • Trit,- the ternary version of a bit, the ternary digit.
  • Tryte – the ternary version of a byte, usually 9 trits wide
  • Ternary Word – a 27 trit wide number.
  • Multiplicand – the number being multiplied
  • Setun – a Series of computers built in Russia on the balanced ternary system