外部記憶装置

脳みそ小さすぎるからメモしとく

リレー式計算機で円周率を計算する その2

丸々1ヶ月ぶりの更新です。命令セットの決定とエミュレーターの作成は進めていたのですが、ブログ更新は完全に放置していました。 早速ですが、今回は計算アルゴリズムの大まかなフロー作成です。

ライプニッツの公式へ変更

前回の記事でマチンの公式を利用すると言っていたのですが、計画を変更しライプニッツの公式を利用することにしました。 理由は以下の計算結果が出たからです。

以下の結果は前回のN(分母)を1000に変更して計算したものです。

./leibniz
Step:252
3148

./machin
Step:5
3152

以上のような結果になったわけです。 何が問題かというと、前回分母を10000に設定したのはリレー計算機を16bitで作成すると考えていたからです。

しかし、8bitでも大変なのに16bitとなるとえげつない量のリレーが必要となり計画の達成が困難になることは明白です。 「多倍長計算」なども一応決めた命令セットをもとにアセンブラで書いてみたのですが、除算の手間を考えると現実的ではありませんでした。 そのため、Nを1000に変更してもライプニッツの公式で314が計算可能であることが分かったため、データバス幅を減らすべく、ライプニッツの公式を利用することにしました。

計算アルゴリズムの大まかなフロー作成

というわけで、ライプニッツの公式を利用することになりました。前回の計算プログラムから無駄な部分を省き改良したものが以下のとおりです。

int main(){
  int result=0;
  int u=1;
  int l=1;
  int step = 1;
  while(u != 0 && l != 0){
    u = 4000/(step*2-1);
    l = 4000/(step*2+1);
    result = u - l + result;
    step += 2;
  }
return result;
}

このプログラムを実行するために必要な命令は大きく分けて、「加算」・「減算」・「乗算」・「減算」・「分岐」 の5つです。1つずつ考えていくことにします。

加算

この命令に関しては何も言う必要は無いと思います。今回の計算に関しては4000以下つまり符号なしで12bitまでの加算が出来ることが求められます。

減算

加算と同様基本的な演算です。今回はデータバス幅の関係上、符号なしの数も扱いたいので補数による減算ではなく、減算器をハード的に実装することになります・

乗算

乗算は加算とシフト、AND命令で全て実現できるのですが、プログラムはかなり長いものになります。 そのため、今回は小さな乗算器をハード実装してソフトウェアで大きな数も扱えるようにする方法でいきます。

除算

除算をハードで実装するとなるとかなり大変なので、これは最初からソフトウェアでエミュレーションすることにします。 幸いなことに多倍長計算は扱わないので比較的に簡単にできそうな気はします。

分岐

このプログラムにおいて最も重要な命令です。whileループの条件式にNon Zero判定を利用し、 除算のソフトウェアエミュレーションでは2数の大小比較の分岐命令を必要とします。 大小比較は比較器によって行うことができますが、今回はリレー数も考慮して 減算命令と正数分岐、負数分岐、0分岐命令を利用することにします。

まとめ

エミュレーターアセンブリで計算プログラムを書いてみた結果、以上のような方針で進めることにしました。 命令セットは大方完成しているのですが、さらに必要・不必要な命令がないか精査して正式に決定したあとで記事にしたいと思います。 エミュレーターも作っていたのですが、初めて作ったこともありスパゲティ状態なので0から作り直したいと思います。