レナード：「無限のシェルドン」？！
シェルドン：無制限のシェルドンは他のすべてのカードを破り、自宅でカードを作ることの禁止に違反しません。
私はまだリレーコンピューターを構築しているので、その機能を同様の趣味のプロジェクトと比較することにしました。
プログラムは自分のコンピューターでのみ実行しました（明らかな理由で）が、残りの部分では、少なくともその複雑さを比較できるように、著者が作成したプログラムをいくつか見つけました。
前回はフィボナッチ数を数えましたので、もう少し複雑なプログラムを続けましょう 。
すべてのコンピューターが成功するわけではありません。たとえば、DUO 14 Premiumは非常に小さく、8ビット数を乗算するプログラムでさえ適合しません。
乗算
現在、8ビットのアルデュインは1つの命令で数値を乗算できます。 70〜80年の間、この機能はほとんどのプロセッサにはありませんでした。 中継コンピューターにはありませんが、
愛好家はそうします。
したがって、通常の加算演算を使用して数値を乗算する必要があります。 もちろん、N（またはM）の繰り返しによるループを使用してMにNを乗算することは価値がありません。 列内の乗算をシミュレートすることをお勧めします。 このようなもの：
\ 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}
ここで、各ステップで、乗算はまだ実行されます（ただし、小さい数ではあります）。 10進数ではなくバイナリシステムで作業する場合は、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}
これには2つの方法があります。 MとNを乗算し、結果をRに書き込みましょう。1つの方法は、サイクルM >> = 1、R + = N（CYの場合）、N << = 1で実行することです。別の方法はR << = 1です。 、M << = 1、R + = N（CYの場合）。 この方法で8ビット数を乗算するには、8回の反復が必要です。
ハリーポーターのリレーコンピューター
ハリーポーターのコンピューター（HPRC）（および彼のフォロワーのコンピューター）では、ALUはレジスターBとCのみをオペランドとして使用します-8つのうち2つしか使用できません。 計算結果は常にレジスタAに格納されます。これはi8080よりもさらに不便です。i8080では、バッテリーがありましたが、オペランドを選択できました。
したがって、HPRCのプログラムでは、追加の出荷がたくさんあります。 8ビット乗算のプログラムは、29バイト（23命令）で構成されています。 長いジャンプ命令はALU操作よりも3倍遅く実行されるため、ここでバイトを個別にカウントしました。
プログラムを開始する前に、係数をレジスタ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
中継コンピューター「トレーナー」
このコンピューターの各命令は、オペランドを読み取り、結果を任意のメモリセルに書き込むことができます。 したがって、プログラムは非常にコンパクトです。
; 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
一握りのリレー
私のコンピューターにもハードウェア乗算演算はありません。 しかし、一方で、ALUはどのレジスタでも動作することができます（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
以下に、2つの小さな数字に対する彼女の作品のビデオを示します。
ユークリッドアルゴリズム
ユークリッドアルゴリズムは、2つの整数の最大公約数（GCD）を見つけるための効果的なアルゴリズムです。 最も単純な場合、ユークリッドアルゴリズムは正の整数のペアに適用され、新しいペアを形成します。このペアは、小さい数と大きい数と小さい数の差で構成されます。 数が等しくなるまでプロセスが繰り返されます。 見つかった数は、元のペアの最大公約数です。
int gcd (int a, int b) { return b ? gcd(b, a - b) : a; }
このようなアルゴリズムのボトルネックは、入力での大きな数と小さな数です。 たとえば、GCD 1および255（8ビットコンピューター）を計算するには、255回の反復が必要です。 より高度なバージョンであるユークリッドバイナリアルゴリズムを適用できます。 このアルゴリズムは、GCD（GCD）の比率を使用します。
次のプログラムで説明します。
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);
このようなアルゴリズムの方が優れています-その動作時間は桁容量に比例します。 しかし、プログラムは非常に長くなることが判明します。つまり、私はまだそれを実装することができません。 したがって、単純な減算アルゴリズムを見てみましょう。
ハリーポーターのリレーコンピューター
残念ながら、ハリーはユークリッドアルゴリズムをエンコードしていませんでした。 結局のところ、「カチカチ」音がする方法をライブで聞くことは機能しません。
中継コンピューター「トレーナー」
ここに参照実装があります-そして、チームの便利なアーキテクチャにより、非常に短いことが判明しました。
; 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, 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） | |
| トレーナー | 10（7） | 11（8） |
| アフォー | 10（7） | 14（11） |
ユークリッドアルゴリズムの実装は、両方のオペランドを0でチェックするため、少し悪くなりました。また、両方のトレーナーアルゴリズムでは、「move if register is 0」などの命令が使用されますが、これはコンピューターにはありません。 作るのは難しくありませんが、事前に考えていませんでした。
次は何ですか
実際、私も除算を検討したかったのですが、そのためのプログラムは18ステップの長さでした。 これまでのところ、ROMのはんだ付けは16セルのみです。 そのため、次回に戻ります。
参照資料
» githubのプロジェクトページ
» コマンドシステムの詳細な説明
» リレーコンピューターの説明の最初の部分
» 説明の2番目の部分
» 説明の3番目の部分
» 説明の4番目の部分