TTL Part the first: 10 bit x 6 bit multiplier

So here we have it...the 10 bit times 6 bit multiplier, put together using Helmut Neemann's excellent Digital - simulator for digital circuits: 

https://github.com/hneemann/Digital 

It's got an excellent in library of 74-series chips. Speaking of which:

Chip count:

17 × 74283 (4-bit full adder)

15 × 7408 (quad AND gate)

plus LEDs (to show amongst other things the partial sums in binary) and the aforementioned TIL311 hexadecimal displays (to show A, B and A × B) - although not strictly needed, these will prove invaluable if/when I get around to real chips and real solder and real mistakes.

And this is what happens when you switch it on (i.e. press the space bar in Digital). The two inputs (upper left) are A = 3F (111111) and B = 3FF (1111111111) and the product (lower left) is FbC1, which is the correct answer 😌.

The partial products (the three sets of LEDs in the middle, respectively) for this example are:

R = 1111111111 + 11111111110 = 0101111111101 (1023 + 2046 = 3069 decimal)

S = 111111111100 + 1111111111000 = 010111111110100 (4092 + 8184 = 12276 decimal)

T = 11111111110000 + 111111111100000 = 01011111111010000 (16368 + 32736 = 49104 decimal)

the sum of these giving the product, 64449 decimal or FbC1.

The intermediate quantity, U = R + S = 0101111111101 + 010111111110100 = 011101111110001, is shown by the lower left row of LEDs.

Some further examples:

3F × 001 = 003F

2A × 2AA = 6FE4

00 × 392 = 0000

34  × 3B3 = C05C

2d  ×  3b5 = 36d1

 

10 bit x 6 bit multiply

So, we need to multiply a 6-bit number (d) by a 10-bit number (b). Like this:

Writing the thing out as a grade-school (i.e. long) multiplication shows what seems like a reasonable approach. Each bit of the ten bit number (multiplicand) is multiplied by the first (right-most) bit of the six bit number (multiplier); this forms the first row - partial product PP0. Next, each bit of the multiplicand is multiplied by the second bit of the multiplier; this forms the second row. This row is shifted one place to the left. This row is partial product PP1. And so on.

We then add together the six partial products, the sum being the product of the two original numbers.

The numbers in red are hexadecimal, those in blue decimal: 1023× 63 = 64449. Hex is easier to read (at least for me!) than binary; I can use 1970s era TIL311 LED hexadecimal displays from Texas Instruments in actual circuitry. At least for intermediate results: the final digits of π will, of course, be decimal 😃.

Multiplication by a single bit is easy enough - an AND gate. To get all six partial products needs sixty gates (that's fifteen 7408 chips). The partial products then get added together with 74283 chips (4-bit binary full adders). We add together PP0 + PP1 to get R, then similarly S and T then need to add R + S = U and finally U + T, to give the product. That's seventeen 7283 chips in total; the 4-bit adders need cascading in groups of 3 or 4 so as to add together numbers with more than four bits, for example adding together PP0 (10 bits) and PP1 (11 bits) needs 3× 4-bit chips, to give the (potentially) 12-bit result (101111111101, as for the example above).

the cheapest science

Four of the more 'interesting' parts of the algorithm are shown circled below. Interesting in the sense of implementation using 1970s TTL chips.

First is the multiplication of a six bit (green) by a ten bit (blue) number, the result being - for our purposes - a 14 bit number (brown). In general of course, the product of a six bit and a ten bit number could be 16 bits (i.e. 1111111111 × 111111 = 1111101111000001), but it turns out that the maximum value that d ever attains (at least when calculating 263 digits of π) is 16371, a 14 bit number (i.e. 11111111110011). Specifically, this maximal value occurs when the product 17 × 963 (10001 = d) × (1111000011 = b) is computed. Importantly, the size of d, when appearing as the multiplicand, is six bits maximum; hence a six bit by ten bit multiplier is sufficient.

Second is the multiplication of an eleven bit number by the decimal value ten (i.e. 1010); an eleven bit by four bit multiplier is needed. The fact that the multiplying factor is constant (ten) rather than an arbitrary 4 bit number, suggests the possibility of some significant simplifications to the circuitry.

Third we have the division of a fifteen bit number (d has now become red), by an eleven bit divisor (g); both quotient and remainder are required. Of all the 'interesting' bits, this sounds the most alarming.

Fourth and finally we have the division of a six bit number (d is now green) by the decimal value ten (i.e. 1010); both quotient and remainder are required.  Both of these quantities are representable by 4 bit values (i.e. kpi and e). The number kpi is either an actual (decimal) digit of π, or ten (and so needs 4 bits maximum).

the digits

Here's the output produced by the spigot algorithm shown in the previous post. Digits are output in groups of three, hence the arrangement shown - the π digits are in the rectangular boxes. The first 263 digits are correct; the 264^th digit is incorrect (it should be a six). The decimal point has been added manually.

So, that's actually seven more digits than the 256 aimed for. And one more decimal place than that computed by W. Lehmann of Potsdam (261 decimals), in 1853 [1].

[1] W. Lehmann, Beitrag zur Berechnung der Zahl π, welche das Verhiltniss des Kreis-Durchmessers zum Umfang ausdriickt, Archiv der Mathematik und Physik, 21 (1853), 121-174.

 

TLC algorithm

There's an elegant method for calculating certain transcendental numbers (like π, e) called a spigot algorithm; "spigot" as in a tap or valve controlling the flow of a liquid (or perhaps a gas?); such an algorithm for calculating the digits of e appeared in a paper by Sale in 1968 [1]. 

Spigot algorithms work with 'nice small integers' and start producing digits (of π in our case) right from the start [2,3], and so seems a good basis for the Transcendental Logic Circuit...

The following algorithm - which will form the heart of the Transcendental Logic Circuit - is a modification of the C spigot program given by Arndt and Haenel [2, p. 83], the aim being to make the thing work with integers that use 15 or fewer bits, producing (at least) 256 digits of π. The colour coding indicates the required size for each variable:

            grey     2 bits

            violet     4 bits

            green     6 bits

            blue     10 bits

            orange     11 bits

            brown     14 bits

            red     15 bits

This level of bit-fastidiousness is not unimportant - unnecessary bits can have dramatic effects on the complexity of the hardware!

l_init and l_carry are logical variables (1 bit).

[1] A. H. J. Sale, The calculation of e to many significant digits, Comput. J. 11 (1968), pp. 229–230.

[2] Jörg Arndt, Christoph Haenel, Pi - Unleashed, Springer-Verlag Berlin, 2nd. ed., 2001, chap. 6.

[3] Stanley Rabinowitz and Stan Wagon, A Spigot Algorithm for the Digits of π, Am. Math. Monthly., Vol. 102, No. 3 (Mar., 1995), pp. 195-203.

Ludwig Wittgenstein and π

“If people never did silly things nothing intelligent would ever get done.” Wittgenstein

The game (i.e. self-imposed challenge) is to make an electronic circuit that calculates a reasonable number* of decimal digits of pi (π) using 1970s TTL integrated circuits^†. Sounds irrational? Absolutely.

*256 seems a good number to aim at.

^†Whatever's in the 1976 edition of the TTL Data Book for Design Engineers (2nd ed.), Texas Instruments.