15 bit ÷ 11 bit - part the third

Wiring of the five stack-up boards is the next step; each board has 65 miniature screw terminals along its edge, plus a power connector:

Boards are kept apart with 35 mm plastic spacers, together with M3 stainless threaded rods (250 mm lengths).

The plan of attack was to interconnect the first two boards, test, then add the third board and so on, at each step cross checking the diagnostic LEDs with the Digital simulation.

The completed brick of five stacked-up boards were then mounted on to the base board and everything hooked up. And so we have the completed 15 bit hardware divider:

Testing of the individual boards and partial builds paid dividends...the completed thing worked first time: here we have C71 (hex) ÷ 439 (hex) = 2, remainder 3FF.

And here we have 7FB8 ÷ 4E7 = 1A, remainder 42 (hex):

And, here we divide by zero; 'wrong', but correct in the sense that it agrees with the Digital simulation...

Total current consumption is about 2.3 amps; the worst-case I've found is 6DB6 ÷ 1  = 6DB6, remainder 0, drawing 2.46 amps. Those old TIL 311 displays eat up about half of that.

Finally, I've had a go at measuring the time taken by the divider. Here, bit 0 of dividend (numerator) N is clocked at 100 kHz; the oscilloscope display (0.1 μs/div) shows quotient (Q) bit 0 following after a delay of about 0.14 μs, giving (perhaps) operation at something like 7 MHz. (For the record, the divisor M = 1, and dividend N = 7FFF or 7FFE, and the oscilloscope vertical display is 2 V/div).

15 bit ÷ 11 bit - part the second

The next step, after constructing the base board, was to start construction of the five stacked-up boards. These are identical; the first one was built and tested, then the next four were built 'in parallel'; it's actually a lot easier making the four subsequent boards, if a little tedious.

Circuit diagrams were printed on A0 paper - the game being to highlight connections once they have been wired on the board.

Here's the completed, yet to be populated board #1:

And the testing of the populated board:

My work space - replete with Herman Miller desk.

And, after about a month of evenings and weekends, we have the five completed boards:

The pink wires supply the 11-bit divisor (M) to all boards; four of the boards have two sets of screw terminals, allowing easy daisy chaining of the divisor wires from board to board.

Amazingly, in all of this constructional complexity, there was just one error - board #2 had a single wire that went to the wrong pin of one of the ALUs. Fault finding wasn't difficult, since it's easy enough to compare expected pin logic states (from Digital simulation), to the actual chip pins. I didn't even have a logic probe; a multimeter was sufficient.

15 bit ÷ 11 bit - part the first

This is the big one: a direct implementation of the unrolled non-restoring division algorithm. A total of seventy chips, including no fewer than forty-eight 74LS181 arithmetic logic units!  

All these chips are organised across six main boards; five of these (which are identical, each dispatching three lines of the long division, and having nine 74181s), are stacked over a base board. The latter (with three 74LS181s) handles the final step of the non-restoring division, namely calculation of the remainder. This board also has the TIL 311 hexadecimal displays, for dividend, divider, quotient and remainder.

Here's the partially wired base board:

And here's the final base board:

A lot of care was taken to test everything for correct operation during construction of the various boards: the twelve discrete LEDs were included to give some diagnostic capability. In the completed divider, if the yellow LED is unlit, the red LEDs show a binary representation of the remainder (this can be seen for the partially wired board above: 555 (hex) = 10101010101 (binary). These sets of twelve LEDs are also included in each of the five (identical) stacked-up boards, allowing some useful testing of each board in isolation.

The four 15-way D-sub connectors are for the dividend, divisor, quotient and remainder, respectively. Interconnects to the stacked-up boards are via the miniature terminal blocks (0.1 inch spacing type).

6 bit × 10 bit multiply

From 31st May 2023 - IC sockets, decoupling capacitors...

to 22nd July 2023...

Here we have 39 × 2CC = 9F6C. The thing almost worked first time - but one of the 74283s had got inserted without its pin 1 (it was inadvertently bent away from the socket)...giving obviously wrong results like 3F × 000 = 0200. Incredibly (given the mess of wiring), that was the only issue.

3 bit × 10 bit multiply

 Probably the second easiest bit of circuitry...

Here we have 7 × 3FF = 1BF9.

Here we have 3 × 61 = 0123.

6 bit ÷ ten (decimal) revisited

Hand soldering of the IDC connectors is proving too fiddly (when constructing the 3 bit × 10 bit multiplier board - see next post), so I've opted to use D-sub connectors, fixed to an aluminium cross piece:

The D-subs are fixed to the cross piece using Richco, PCB MB 01 mounting blocks and M3 self tappers. The cross piece is fixed to the rail pieces using Richco HTSB M3-9-5-2 9 mm threaded standoffs. 

I like this approach - looking mainframe-esque:

First hardware: 6 bit ÷ ten (decimal)

First attempt, on a 220 mm × 100 mm (ROTH ELEKTRONIK - RE310-S2) - appropriately named LABOR CARD, ended in early abandonment; it was becoming way too cramped.

So, my new approach is to use 3 off (or, for some boards, 4 off) 100 mm × 150 mm boards (FR4), assembled into a 'tray'. Two 10 mm × 10 mm × 1 mm aluminium angles form the tray; the boards are attached via nylon PCB mounting blocks (Richco: PCB MB 01) and 3/4 inch M3 (No. 4) self tappers:

The aluminium rails will help when it comes to a final assembly of the thing - it's anticipated that they will slide into some type of card guide, so that several trays can be stacked up. Probably something like 27 trays in total.

And so we have:

Board power (5 V) comes in bottom right; power indicator top left. There's a 6u8 (35V!) solid tantalum capacitor, plus 100 nF ceramics next to each chip. Data in/out via IDC connectors.

I simply love the old TIL 311 hexadecimal displays (although they draw something crazy like 90 mA each!). 

And here have 3F ÷ A = 6, remainder 3. Amazingly, this all worked first time!

Total current consumption is 420 mA max - depending on what's displayed. If/when I get the whole thing working, I can pull the display chips - they wouldn't be readable anyway, when the boards are stacked up - included for the moment for test purposes.

All the chips are LS, except for the 7425 (dual 4-input NOR), which is the basic Texas SN7425N; I couldn't find the LS version of this one.

An exception

I have found one case where the TLC algorithm does not give the 'expected' result. By 'expected' I mean the value given by

The exception occurs when operator ⊡ is equal to PLUS, i.e. the ALU(9,1) case, and γ = 1. The expected result is

However, the TLC algorithm yields something different, for example:

The algorithm yields rational values, which are close to the expected 1/α value.

It's conjectured that, for the ALU(9,1) with γ = 1 case, the actual value given by the algorithm is given by

where b is a parameter in the TLC algorithm (see post of 18th December 2021). Hence, 

It is evident that the larger the value of b, the closer the algorithm's value is to the expected 1/α value. A value of b = 888 was used for the above.

The rational value and that produced by the algorithm agree to large numbers of digits. For example, for the α = 2 example (i.e. 219780/439561), the rational value and the algorithm's value agree to at least 5000 digits; this may reflect the fact that the value is a repeating decimal (period 525).

Finally, we look at the effect that parameter b has on the calculation of  π:

There's a little blip at b = 888; this gives 265 correct decimal places. That's actually two more correct digits than given in the 25th September 2021 post; that result took b = 1023.

Hence there appears to be an optimum value of b - at least for the π calculation.  The TTL implementation allows the user to set b to any particular value.

As mentioned in a previous post, the actual values produced by the TTL implementation may differ from that produced by the above expressions for P and Q, due to the fact that the TTL implementation necessarily uses limited bit widths.

First discovery

Previously, it was mentioned that setting ALPHA = 1, GAMMA = 1, BETA = 10 and omitting the d = d * b operation (OP#1) (as for the calculation of e), and using the exclusive or operation, yields

1.543080634815243778477905620757061682601529112365863704737402...

which happens to be cosh(1).

Hence we state the interesting identity:

where ⊕ means exclusive or, and we replace 1 ⊕ 1 = 0 with 1 (to avoid dividing by zero).

The product in the denominator gives 1, 3, 6, 30, 120, 840, 5040... which is A265376 in the The On-Line Encyclopedia of Integer Sequences (OEIS), Published electronically at http://oeis.org. The proof that the above identity is true is straightforward: even terms of the denominator equal (2n-1)! + (2n)! and odd terms equal (2n-1)!. The former sum to 1/e and the latter to sinh(1), and we recall cosh(1) = 1/e + sinh(1).

And there's plenty more of this type of thing, for example (i.e. setting ALPHA = 4, GAMMA = 4, BETA = 10) gives the following:

Although there might seem to be a preponderance for the exclusive or operation to yield values writable in terms of hyperbolic functions, this is not always the case, for example:

Beautiful methods of reckoning

After a bit of thought, I've managed to come up with two expressions that define exactly what it is that the TLC algorithm (described earlier) computes.

For a given ALPHA, BETA and GAMMA, the algorithm computes one of the following two quantities. P if the d = d * b operation (OP#1) is included, and Q if it is omitted.

In the above, the ⊡ symbol means an arithmetic/logical operator; for the TLC project it's one of those implemented by the 74181 arithmetic logic unit, as listed in the previous post. To avoid division by zero, instances for which γk ⊡ α = 0 are replaced with unity.

(Numerical experiments suggest that the above expressions work for all the arithmetic/logical operations supported by the 74181 as listed in the previous post. An obvious (unanswered) question is this: what other operations does the algorithm work for?)

So, for example, for the π calculation operator ⊡ is A MINUS B (i.e. ALU row 6, column 2). And we set ALPHA = 1, BETA = 20 and GAMMA = 2, and thus compute the quantity given by

where operation OP#1 is included (i.e. in this mode the upper of the two equations is computed (P)). 

Omitting OP#1 (i.e. the lower of the two equations is computed (Q)), gives

where erf (x) is the error function. The first 2504 digits of the value produced by the TLC algorithm are correct. (This constant is mentioned in Finch, Mathematical Constants: 94 (Encyclopedia of Mathematics and its Applications), p. 423.)

Note: the TTL implementation of the TLC algorithm represents the algorithm's different variables using various limited numbers of bits - for example the d = d * b operation (OP#1) uses a 6 bit times 10 bit multiplier to yield a 15 bit result (bit 16 is ignored). This means that the actual value produced by the TTL implementation may differ from that produced by the above expressions for P and Q. This is not always the case, however - the algorithm produces 266 correct digits of π, with or without the TTL implementation's finite bit widths (with parameter b = 888).

On the other hand, ALU(9,1) (i.e. PLUS operation), with ALPHA = 1, BETA = 10, GAMMA = 1, and OP#1 enabled, yields

0.9989875126560917988525143... = 2960/2963 (no limitation on bit width)

and 

1.2202931302994487041321361... (TTL implementation).

As discussed in a later post (26th November), neither of these values agrees with the 'expected' result (unity).

Something interesting

The value g = GAMMA * b ± ALPHA is obtained using the three bit times ten bit multiplier (to give the GAMMA * b), and three 74181 arithmetic logic units to make the addition or subtraction.

But, the 74181 ALUs can do more than addition or subtraction...

Here, I've labelled up the rows and columns: discounting duplicates, there are some 38 different arithmetic/logic operations that are possible. The addition of six switches allows any of these different operations to be used:

Hence the thing calculates g = ALU(row,col,A,B), where row and col are the row and column as per the table above, and A = GAMMA * b and B = ALPHA.

So, we have g = ALU(6,2,A,B) = A MINUS B = GAMMA * b - ALPHA; if we set ALPHA = 1 and GAMMA = 2 (with BETA = 20) we get 3.14159265358979323846264338...

But how about something more exotic?

g = ALU(6,0,A,B) = A ⊕ B = GAMMA * b ⊕ ALPHA, where ⊕ is the exclusive or operation.

Setting ALPHA = 1, GAMMA = 1, BETA = 10 and omitting the d = d * b operation (OP#1) (as for the calculation of e), we get

1.543080634815243778477905620757061682601529112365863704737402...

which happens to be cosh(1). The first 2,236 digits of this result are correct. Discovering that this value is cosh(1) wasn't difficult: I just searched for '1.543080634815' on Google!

And there's a lot more of this type of thing...

...another example: ALPHA = 1, BETA = 5, GAMMA = 1, with ALU(1,2) = A | B = GAMMA * b | ALPHA, where | is logical or; operation (OP#1) (again, as for the calculation of e), we get

0.331224981744493362805940652824580844936569932976054216288429...

This equals I₁(1) + I₀(1) - 3/2 , where I₁ and I₀  are modified Bessel functions of the first kind. The result from the algorithm is correct to more than 2000 digits.

Showing that the above is indeed the sum of a couple of Bessel functions requires substantially more effort than typing a number into Google. More on this later.

Interestingly, it seems that perhaps all the 38 possible ALU configurations yield 'proper' values, some more 'interesting' than others; I'd naively assumed that the logic operations would not produce anything meaningful, but this appears not to be the case at all.

I'll end this post with another bizarre example:

ALPHA = 15, BETA = 10, GAMMA = 1, with ALU(11,0) = A & B = GAMMA * b & ALPHA, where & is logical and; operation (OP#1) (again, as for the calculation of e), we get

1.718281828461073178906616813933686139831054397588246567510596...

It looks like e - 1 = 1.71828..., but it isn't (the numbers differ at the eleventh decimal place).

Rather, the value appears to be equal to

2246953104077 / 1307674367999 

where, even more interestingly, the denominator equals (15! -1). The computed value (1.71828...) and the rational value agree to 672 digits.

GitHub

The complete set of schematics can be found here:

https://github.com/pac-mcnair/spigot-machine

(.dig (Digital) files, .svg files and PDFs)

By omnibus I traveled to Brooklyn

Setting GAMMA = 1, BETA = 10, ALPHA = -1 and omitting the d = d * b operation (OP#1), the machine pops out:

...and so on. The first 2,232 digits are correct, as far as the 369. Then we get 975; the correct digits are 882.

The machine has a counter that displays the total number of triplets output - for the above, the count is 745 = 2235 digits have been output.

It's not that fast: the Digital simulation took about five hours(!) to get to triplet number 745. When the simulation's running, there's a little '3 kHz' at the bottom left of the Digital screen - not sure what this means/indicates...but it'll be interesting to see how fast/slow the actual circuitry is in practice.