自作TTLコンピュータで円周率を計算する（第２話）
乗除算を加減算に書き換えた
本サイトは1970年代にオリジナルCPUの設計と、そのCPUを使ったコンピュータの自作を夢見ていた青年(当時)が40年の月日を経て、完成させたＴＴＬコンピュータ、RETROF-8のソフトウェア作成編です
本サイトは1970年代にオリジナルCPUの設計と、そのCPUを使ったコンピュータの自作を夢見ていた青年(当時)が40年の月日を経て、完成させたＴＴＬコンピュータ、RETROF-8のソフトウェア作成編です
プログラムの移植とは、あるプログラムを異なるハードウエアで動かすためのコード変換を意味します。WinXP用のアプリをWin7用に移植する等がその典型例です。他にもWin32用のドライバをWin64用に書換えたり、ファミコンソフトをスマフォ用に書換えるのも「移植」です。
何れの場合も移植先は「新しいハード」であるのが常識の様です。自分で言うのも何ですが、32bitマシン上で動いているプログラムを、加減算しかできない手作りの貧弱8bit機に移植するのは明らかに尋常ではありません。参考になる論文や資料は勿論、類似するノウハウすら見つかりませんでした。ここから先は完全に唯我独尊・自己満足の世界です。学校が教えるプログラミングや、企業が推奨するプログラミングとは、明らかに一線を画しますので、その点を十分ご理解の上お読み頂ければ幸いです。
【注意】下記プログラムはmain()のみを抜粋。このままコピペしてもコンパイラは通りません。円周率編第１話にコピペでコンパイル可能なプログラムを掲載していますので、そちらをご利用ください。
void main(void) {
unsigned short i,j,n,nom[ARRAYMAX]; // ARRAYMAX = 512
for(i=0; i < ARRAYMAX; ++i) nom[i] = 2;
for( i = ARRAYMAX-1; i > 0; --i) {
n=0;
for( j = i-1; j > 0; --j) {
n = n * j + nom[j] * 10;
nom[j] = n % (2*j-1);
n = n / (2*j-1);
}
dig[ARRAYMAX-i-1] = n;
}
debug_print(0,ARRAYMAX) ; //引数で任意範囲を表示可能にしました
}
以下が、乗除算と剰余算を加減算の繰り返しに置換したプログラムです。「＊」と「／」と「％」の3つの演算子が消え、代わりにfor文が２つとワーク変数が２つ(kとm）が増えていますが、アルゴリズムの骨格は変えていませんので、実行結果は変更前と全く同じです。
void main(void) {
unsigned short i,j,k,n,m,nom[ARRAYMAX]; // ARRAYMAX = 512
for(i=0; i < ARRAYMAX; ++i) nom[i] = 2;
for( i = ARRAYMAX-1; i > 0; --i) {
m=0;
for( j = i-1; j > 0; --j) {
for(n=0,k=0;k< j;++k) n+=m; //A ここは何回実行？
for(m=0,k=0;k<10;++k) m+=nom[j]; //B ここは何回実行？
m+=n;
n=j+j-1;
for( k=0;m>=n;++k) m-=n ; //C ここは何回実行？
nom[j] = m;
m = k;
}
dig[ARRAYMAX-i-1] = m;
}
debug_print(0,ARRAYMAX) ; //引数で任意範囲を表示可能にしました
}
今回、アルゴリズムの確認に使っているマシンのCPUは、私のHNと同じCore2duo 6750です。
１世代前のCPUですが、今回の円周率計算程度のプログラムならほぼ瞬間的に完了します。実行時間を気にする必要は皆無です。
しかし、ターゲットマシンはあくまでもクロックが1MHzにも満たない激貧マシンです。クロックの比較だけでも数千倍の差があります。加えて10000×10000の計算もC2Dなら数クロック（実際には多段パイプラインが働き１クロック程度）で実行できますが、乗算命令もシフト命令もないマシンでは10000×10000の計算は10000回足し算を行う必要があります。しかもRETROF-8は１つの足し算だけでも8クロックを必要とします。
Windowsマシンでは１秒以下で終わるプログラムも、RETROF-8では何億秒、何百億秒も要する可能性は十分にあります。 １日は約10万秒ですから、百億秒は１0万日（３0年！）です。正しいプログラムが完成して実行を開始できたとしても、結果を知る前に私の寿命が来てしまいます。これはさすがに困りますので、おおよその実行時間の予測は絶対に立てておく必要があります。
最も内側のループの実行回数を数えるのが、全体の実行時間を予測する際の常套手段です。
上記のプログラムでは、コメントでA,B,Cと書いたコードが一番内側のループに相当します。
実際にカウンターを挿入し（++a; とか書いて,最後にaをprintf()する古式豊かな方法です）確認した所、Ａ/Ｂ/Ｃそれぞれ、22238620回/1303050回/1158000回でした。
Aが約2000万回と圧倒的に多いのでBとCの実行時間は誤差範囲と考え、Aを一回行うのに要する時間に2000万を掛ければ全体の実行時間のおおよその予測が可能と判断しました。
Aを１回通過するのに要する命令数はおそらく30〜50程度だと思います。ここでは50と仮定し、約10億命令の実行で本プログラムは完了すると予想を立てました。
RETROF-8は全ての命令が８クロックで実行されます。従って10億命令の実行時間は80億クロックに等しくなります。この記事を書いている時点では、クロックの最高速度を上げるための処置（バイパスコンデンサの追加やノイズ対策）は全く行っていませんが各命令のテストプログラムが750KHzで動作することは確認できています。計算を簡単にする為に１クロック800KHzでの安定稼動が実現できるとすると、80億クロック÷800KHz＝16,000,000,000÷800,000＝１0,000(秒）となります。
超概算ですが、10000秒、すなわち超激貧TTLコンピュータで円周率を150桁を求めるのには約3時間必要という結論に達しました。
もちろん、これから作業を予定しているハードの調整でクロックアップが図れる可能性もありますが、数時間要することは確かです。まあ30年は待たなくてもよさそうなので一安心しましたが、現在何％程度完了したかを伝える「プログレスバー」の様な機能（OUT命令でLEDに表示する）も作成せねば精神衛生上良くなさそうです。(動いているのか、固まっているのかの区別が必要です)
そもそも、8bitマシンで、unsigned short int を実装できるのでしょうか？
インデクスレジスタどころか、汎用レジスタもないマシンで配列処理ができるのでしょうか？
頭が痛くなってきました。（諦めてヤケ酒を飲んで酔っ払っていなければ、次回に続く）