Леонард: «Беспредельный Шелдон»?!
Шелдон: «Беспредельный Шелдон» бьёт все остальные карты и не нарушает запрет на изготовление карт в домашних условиях, потому что я сделал эту на работе.

Я всё ещё строю релейный компьютер, и поэтому решил сравнить его возможности с похожими хобби-проектами.

Запускал я программы только на своём компьютере (по понятным причинам), но и для остальных нашёл несколько программ, написанных авторами, чтобы можно было сравнить хотя бы их сложность.

Числа Фибоначчи мы уже считали в прошлый раз, поэтому продолжим с программами чуть посложнее.

Не со всеми компьютерами это получится, например DUO 14 Premium совсем маленький и даже программы для умножения 8-битных чисел туда не влезут.



Умножение


Сегодня умножать числа одной инструкцией умеет любая восьмибитная ардуина. В 70-80 годы этой возможности в большинстве процессоров не было. Нет её и в релейных компьютерах,
которые делают энтузиасты.

А значит, числа надо перемножать, используя обычные операции сложения. Конечно, умножать M на N используя цикл на N (или M) итераций не стоит. Лучше сымитировать умножение в столбик. Примерно вот так:

$\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}$


Тут на каждом шаге всё равно делается умножение (хоть и на маленькое число). Если же работать в двоичной системе вместо десятичной, то умножать придётся или на 0, или на 1. Оба случая тривиальны: x * 0 = 0, x * 1 = 1. Остаётся лишь сдвинуть результат частичного умножения на несколько позиций влево, а потом всё сложить.

$\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}$


Можно делать это двумя способами. Пусть мы перемножаем M и N, а результат записываем в R. Тогда один способ — это выполнять в цикле M >>= 1, R += N (если CY), N <<= 1. Другой способ — R <<= 1, M <<= 1, R += N (если CY). Чтобы так умножить восьмибитное число, надо сделать восемь итераций.

Harry Porter's Relay Computer




У компьютера Гарри Портера (HPRC) (а также у компьютеров нескольких его последователей) АЛУ использует в качестве операндов исключительно регистры B и C — всего 2 из 8 доступных. Результат же вычислений всегда помещается в регистр A. Это ещё неудобнее, чем у i8080, где хоть и был аккумулятор, но операнды можно было выбирать.



Поэтому в программах для HPRC появляется много лишних пересылок. Программа для 8-битного умножения состоит из 29 байт (23 инструкции). Я посчитал здесь байты отдельно, потому что длинные инструкции перехода выполняются втрое медленнее операций АЛУ.

Перед началом выполнения программы множители должны храниться в регистрах B и C, а результат она записывает в регистр 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»




Каждая инструкция этого компьютера может читать операнды и записывать результат в произвольную ячейку памяти. Поэтому программа получается довольно компактной.

; 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




В моем компьютере тоже нет никаких аппаратных операций умножения. Но зато АЛУ умеет работать с любыми регистрами (можно даже поксорить PC с чем-нибудь), поэтому программа умножения тоже получается небольшая.

 ; 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

Вот видео её работы для двух небольших чисел:


Алгоритм Евклида


Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя (НОД) двух целых чисел. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

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

Узкое место такого алгоритма — большое и маленькое число на входе. Например, для вычисления НОД 1 и 255 (восьмибитный же компьютер) потребуется 255 итераций. Можно применить более совершенную версию — бинарный алгоритм Евклида. Этот алгоритм использует соотношения для НОД (GCD):

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



Он иллюстрируется следующей программой:


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);

Такой алгоритм получше — время его работы пропорционально разрядности чисел. Но программа получится очень длинная, а значит пока что реализовать её у меня не получится. Поэтому посмотрим на простые алгоритмы с вычитанием.

Harry Porter's Relay Computer


К сожалению, Гарри не закодировал алгоритм Евклида, а делать это самому мне не захотелось. Ведь вживую послушать как она будет «тикать» не выйдет.

Relay computer «trainer»


Здесь эталонная реализация есть — и она получается также довольно короткой из-за удобной архитектуры команд.

; 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


Для своего компьютера я смог не только написать программу, но и запустить её. Ниже на видео результат выполнения с трассировкой инструкций (в виде субтитров).

; 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


Какой компьютер лучше?


В таблице ниже — число инструкций для каждой из программ. В скобках указано число инструкций, необходимых непосредственно для вычислений, а не для загрузки операндов или остановки.
Компьютер Умножение Алгоритм Евклида
HPRC 25 (23)
Trainer 10 (7) 11 (8)
AFOR 10 (7) 14 (11)

Моя реализация алгоритма Евклида получилась чуть похуже из-за проверки обоих операндов на 0. Также в обоих алгоритмах Trainer'а используется инструкция типа «перейти, если регистр равен 0», которой в моём компьютере нет. Сделать ее было бы несложно, но заранее я об этом не подумал.

Что дальше


Вообще-то я хотел рассмотреть ещё и деление, но программа для него получилась в 18 шагов длиной. А напаял я пока только 16 ячеек ПЗУ. Поэтому вернёмся к нему в следующий раз.

Ссылки


» Страница проекта на github
» Подробное описание системы команд
» Первая часть описания моего релейного компьютера
» Вторая часть описания
» Третья часть описания
» Четвёртая часть описания