Mini benchmark home relay computers

Leonard: "Boundless Sheldon" ?!
Sheldon: "The Unlimited Sheldon" beats all other cards and does not violate the ban on making cards at home, because I did this at work.

I am still building a relay computer , and therefore I decided to compare its capabilities with similar hobby projects.

I started the programs only on my computer (for obvious reasons), but for the others I found several programs written by the authors so that at least their complexity could be compared.

We already considered the Fibonacci numbers last time , so we’ll continue with the programs a bit more complicated.

Not all computers will succeed, for example, the DUO 14 Premium is quite small and even programs for multiplying 8-bit numbers will not fit there.
')

Multiplication

Today, every eight-bit arduin can multiply the numbers with one instruction. In the 70-80 years, this feature was not available in most processors. It is not in relay computers,
who make enthusiasts.

So, the numbers must be multiplied using the usual addition operations. Of course, multiplying M by N using a loop by N (or M) iterations is not worth it. It is better to simulate the multiplication in a column. Like this:

\ begin {array} {ccccc} && 1 & 2 & 3 \\ & \ times & 4 & 5 & 6 \\ \ hline && 7 & 3 & 8 \\ & 6 & 1 & 5 \\ 4 & 9 & 2 \\ hline 5 & 6 & 0 & 8 & 8 \ end {array}

$\ begin {array} {ccccc} && 1 & 2 & 3 \\ & \ times & 4 & 5 & 6 \\ \ hline && 7 & 3 & 8 \\ & 6 & 1 & 5 \\ 4 & 9 & 2 \\ hline 5 & 6 & 0 & 8 & 8 \ end {array}$

Here at each step multiplication is done anyway (albeit by a small number). If we work in the binary system instead of decimal, then we will have to multiply either by 0 or by 1. Both cases are trivial: x * 0 = 0, x * 1 = 1. It remains only to shift the result of the partial multiplication by several positions to the left, and then everything add up.

\ begin {array} {ccccc} && 1 & 0 & 1 \\ & \ times & 1 & 1 & 0 \\ \ hline && 0 & 0 & 0 \\ & 1 & 0 & 1 \\ 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 0 \ end {array}

$\ begin {array} {ccccc} && 1 & 0 & 1 \\ & \ times & 1 & 1 & 0 \\ \ hline && 0 & 0 & 0 \\ & 1 & 0 & 1 \\ 1 & 0 & 1 \\ \ hline 1 & 1 & 1 & 1 & 0 \ end {array}$

You can do this in two ways. Suppose we multiply M and N, and write the result to R. Then one way is to perform in the cycle M >> = 1, R + = N (if CY), N << = 1. Another way is R << = 1 , M << = 1, R + = N (if CY). In order to multiply an eight-bit number in this way, eight iterations must be done.

Harry Porter's Relay Computer

At the computer of Harry Porter (HPRC) (and also at the computers of several of his followers), the ALU uses only the registers B and C as operands - only 2 of the 8 available. The result of the calculations is always placed in register A. This is even more inconvenient than that of the i8080, where, although there was a battery, you could choose the operands.

Therefore, in the programs for the HPRC appears a lot of unnecessary shipments. The program for 8-bit multiplication consists of 29 bytes (23 instructions). I counted here the bytes separately, because the long transition instructions are executed three times slower than the operations of the ALU.

Before the start of the program, the multipliers should be stored in registers B and C, and it writes the result to register X.

Address Instruction 00 Y=B 01 X=0 02 A=¬B 03 BNEG Else 06 X=C Else: 07 A=-7 08 D=A Loop: 09 B=X 0A A=B<<1 0B X=A 0C B=Y 0D A=B<<1 0E Y=A 0F B=Y 10 A=¬B 11 BNEG Else2 14 B=X 15 A=B+C 16 X=A Else2: 17 B=D 18 D=B+1 19 BNZ Loop 1C HALT

Relay computer "trainer"

Each instruction of this computer can read operands and write the result in an arbitrary memory cell. Therefore, the program is quite compact.

 ; This program multiplies two 8-bit numbers and produces a 8-bit result org 0x00 argx skip 1 argy skip 1 res_lo skip 1 ; Result low count skip 1 org 0x10 mul st #15, argx ; Initialize X st #10, argy ; Initialize Y st #0, res_lo st #-8, count loop lsl res_lo lsl argy jcc skip addto argx, res_lo skip incjne count, loop halt

A fistful of relays

There are no hardware multiplication operations in my computer either. But on the other hand, the ALU can work with any registers (you can even use a PC with something), so the multiplication program also turns out to be small.

  ; C, D - operands, A - result MOVI C, op1 MOVI D, op2 MOVI A, 0 Loop: SHR C, C JMP NC, Next ADD A, A, D Next: ADD D, D, D OR F, C, C JMP NZ,Loop HALT

Here is a video of her work for two small numbers:

Euclidean algorithm

Euclidean algorithm is an effective algorithm for finding the greatest common divisor (GCD) of two integers. In the simplest case, the Euclidean algorithm is applied to a pair of positive integers and forms a new pair, which consists of a smaller number and the difference between a larger and a smaller number. The process is repeated until the numbers become equal. The number found is the greatest common factor of the original pair.

 int gcd (int a, int b) { return b ? gcd(b, a - b) : a; }

The bottleneck of this algorithm is a large and small number at the entrance. For example, to compute GCD 1 and 255 (an eight-bit computer), 255 iterations would be required. You can apply a more advanced version - the binary Euclidean algorithm. This algorithm uses ratios for gcd (gcd):

G C D (2 a, 2 b) = 2 G C D (a, b), G C D (2 a, 2 b + 1) = G C D (a, 2 b + 1), G C D (a, b) = G C D (a b, b), b l e a

$GCD (2a, 2b) = 2GCD (a, b), \\ GCD (2a, 2b + 1) = GCD (a, 2b + 1), \\ GCD (a, b) = GCD (ab, b) , b \ le a$

It is illustrated by the following program:

 m = a; n = b; d = 1; while (m && n) { if (m % 2 == 0 && n % 2 == 0) { d *= 2; m /= 2; n /= 2; } else if (m % 2 == 0 && n % 2 == 1) { m /= 2; } else if (m % 2 == 1 && n % 2 == 0) { n /= 2; } else if (m >= n) { m -= n; } else { n -= m; } } result = d * (m + n);

Such an algorithm is better - the time of its operation is proportional to the digit capacity of numbers. But the program will be very long, which means that for the time being I will not be able to implement it. Therefore, we look at simple algorithms with subtraction.

Harry Porter's Relay Computer

Unfortunately, Harry did not encode the Euclidean algorithm, and I did not want to do it myself. After all, live to hear how it will "tick" will not work.

Relay computer "trainer"

Here the reference implementation is there - and it turns out to be also rather short due to the convenient command architecture.

 ; Euclid's algorithm using repeated subtraction org 0x00 a skip 1 ; First number b skip 1 ; Second number tmp skip 1 ; Tmp variable org 0x10 euclid st #144, a ; Initialize A st #233, b ; Initialize B euclop jeq b, eucdon ; Done ? st a, tmp rsbto b, tmp ; A - B -> TMP jls tmp, over ; A <= B ? rsbto b, a ; A - B -> A jmp euclop over rsbto a, b ; B - A -> B jmp euclop eucdon halt

A fistful of relays

For my computer, I was able not only to write a program, but also to launch it. Below on the video is the result of the execution with tracing instructions (as subtitles).

 ; A, B - operands, A - result MOVI A, op1 MOVI B, op2 LOOP: OR F, A, A JMP Z, END OR F, B, B JMP Z, END SUB F, A, B JMP C, L1 SUB A, A, B JMP LOOP L1: SUB B, B, A JMP LOOP END: ADD A, A, B HALT

Which computer is better?

In the table below - the number of instructions for each program. The number of instructions required for the calculations, and not for the operand loading or stopping, is indicated in parentheses.

Computer	Multiplication	Euclidean algorithm
HPRC	25 (23)
Trainer	10 (7)	11 (8)
Afor	10 (7)	14 (11)

My implementation of the Euclidean algorithm turned out to be slightly worse due to checking both operands by 0. Also, in both Trainer algorithms, the instruction is used, such as “go if the register is 0”, which is not in my computer. Make it would be easy, but I did not think about it in advance.

What's next

Actually, I also wanted to consider the division, but the program for it turned out to be 18 steps long. And while I soldered only 16 ROM cells. Therefore, we will return to it next time.