赤げふの数学

数学・物理・微分の高校生 赤げふのBLOG

Minecraft Redstone D-CCA Multiple&Division(part2)

こんにちはヽ(^0^)ノ

この記事はpart1の続きなので、読んでなければ先ずpart1から見て欲しいです。

乗除算について解説していきます。

 

 

この連続加算器は6tick周期でパイプライン演算をしているので時刻毎に割り当てられた6個の連続加算を同時並行でできるが、乗除算を行う際はそのうち2区画を使っておこなう(工夫すれば3個同時並行でできる)。

以後tickはrstickのことを指すとする。

 

昔私は乗除算をこのDCCA(decimal carry cancel adder)上で同じ手法でできる方法を思いついたので解説する。DCCAの桁数は上限の13桁が出力の限界だが、理論上最大誤差が50(最下位桁が1の位として)出るので出力の有効数字は11桁であるが、平均的な誤差は10程度で済む。

この計算機では小数点の位置をあまり自由に動かすことが出来ないため、入出力の形式は

A×B\cdots 0≦ A\lt 10, 0≦B\lt 10,0\lt AB\lt 100、有効数字12

A÷B\cdots 0≦A\lt 10 ,0\lt B\lt 10,0\lt A÷B \lt 10

 


先ず除算X÷Yについて見るが、手順は筆算ベースであり、X=6.91、Y=2.73を例に取って見ていく(ちなみにB_{12}=-\frac{691}{2730}はベルヌーイ数)

 

f:id:AkaGhef:20200715222214j:image

 

中段の1450,85などの数字は部分剰余と言い、無限小数である場合は部分剰余を割る操作を永遠と繰り返すことになるが、計算機は途中で打ち切る。簡単の為に加算器は13桁ではなく6桁とし、小数点は無視する。Aは部分剰余で初期値は被除数X、Bを除数Y(をシフトしたもの)、Iは商をカウントするためのインクリメント[デクリメント]の±1であり、Oは(暫定的な)商で、初期値は0ある。筆算と少し違う点が、次の段の部分剰余を求める際にAからB×(0〜9)を引くのでは無く、AからBを何回か引いて行う点であり、乗算を使わずに済み、0~9の値を見積もる必要が無い。
AからBを引く度にOにIを足すことで商をカウントしている。これを繰り返しAからBを引きすぎたら一旦BAに足して修正して、OからIを引いてカウントをバックしている。これで次の段の部分剰余が求まるので、BとIを1つシフトダウンしてまた次の段の部分剰余を求める操作を行う。ループは以下の手順。

(1)AからBを負の数になるまで0~9回引く(赤線)
(2)引く毎にOIを足し、商をカウント(赤線)
(3)Aが負の値になったらBを足す(緑線)
(4)OからIを引き、カウントをバック(緑線)
(5)BとIを1つシフトダウン(青線)

 

f:id:AkaGhef:20200715222406j:image

 

次に乗算X×Yについて、被乗数X=4.56、乗数Y=1.23を例にとって見ていく。

[筆算]

 

 

f:id:AkaGhef:20200630072408j:image

 

3つの数を同時に足しあげるのは計算機的に困難なので2数ずつ足しあげる筆算の書き方をしているが、雰囲気は掴んで貰えるだろう。途中で出てくる456,5472の数字の段(緑矢印)を部分和と呼び、除算同様に小数点は無視する。Aは乗ずる回数の書かれた数で初期値は乗数YBは被乗数X(をシフトしたもの)、Iは乗ずる回数をAからカウントダウンするためのインクリメント[デクリメント]の±1である。Oは部分和の役割で、最終的に積X×Yの答えとなる。
AからIを引いてカウントダウンし同時にOにBを加える操作をAが負になるまで行う。Aが負になるとカウントし過ぎなのでAにIを加え、OからBを引き修正する。これで部分和が求まったので次の段の部分和を求める為にBとIを1つシフトダウンする。ループをまとめると以下のようになる:

(1)AからIを負になるまで引く(赤線)
(2)引くごとにOにIを足す(赤線)
(3)Aが負の値になったらIを足す(緑線)
(4)OからBを引く(緑線)
(5)BとIを1つシフトダウン(青線)

[表]

f:id:AkaGhef:20200715232031j:image

乗除算の類似性と実際の回路の手順について説明していく。図や、乗除算それぞれで示したループの手順を見るとほぼBとIを入れ替えただけで、処理内容がとても似ていることが分かる。そこで連続加算器がパイプライン処理であったことを巧妙に使って、
計算機のコア内に入っているOとAにタイミングよくBとIを入力することで乗算と除算を使い分けることが出来る。加算器は6tick周期なのでそれと同期できるようにBとIを保存する外部のメモリは6tick周期で巡回するコンパレータの構造となる。
パイプライン処理で同時に3個の乗除算を行えるが本解説では1個の乗除算のみに限定し更に高速化を試みる。先程ループの手順を示したが(5)のBとIをシフトダウンする際、6tick周期のメモリの場合

シフトする部分に信号が回ってくるまで待つ必要があるためシフトダウンする部分で遅延が生じて、[表]での緑,青の部分の処理をした後の赤の部分の処理に入力が間に合わない。そこでメモリを2tick周期にしてみると、連続加算器の周期が6tickで、2tickはその約数となっているため、2つのスロットにB,Iを入れておくと問題なく処理できる。そしてB,Iが奇数時刻か偶数時刻にコアに入力されるかどうかで乗算と除算を切り替えられる。(これを閃いた時はまさに最適解だったのでめちゃ嬉しかった)


制御回路で実際に動かしていく方法を見る。今手元に制御回路が完成された乗除算器が無く、申し訳ないが忙しいせいで載せることが出来ない。

f:id:AkaGhef:20200715222825j:image
前回補数の項目で話をしたように、減算結果が負であるかどうかは、減算したときに最上位の繰り上がり出力(以後C^Oと書く)がC^O=1ならば結果は0以上である。乗算の場合A-Iの減算をしたときC^O=1ならば減算結果が0以上なので次は赤色の矢印の操作を行い、減算か加算かを制御する(J)の配線をonにして次も減算を行う。逆にC^O=0のとき減算結果が負なので青,緑の矢印の操作を行う、すなわち(J)の信号をoffにし次は加算モードにして、(K)に信号を送ってB,Iを1つシフトダウンする。また除算の場合は、上記のA-IA-Bに読み替えると全く同様の処理であることが理解出来る。
((J)に信号を送る部分を最小遅延で行える回路の実現がかなり大変で2ヶ月も苦労したんですよね)

以上の手続きをアセンブリ風に書いてみる(だいぶ前に書いたものなので正当性怪しいのでお気持ち程度に...)

アセンブリは、デカい命令が書いてある主記憶装置、演算を行う部分、演算結果を記憶する部分(以下Acc)、の3つに分かれる。命令はadd・subで番地指定した所の値をAccに加えたり引いたり

基本番地が低い所から命令を実行していく。
loadは指定した番地から値を引き出し、Accに上書き。
atoreは指定した番地にAccの値を上書き。
jumpは指定した番地から処理を始める。
jump minusはAccの値が負ならjumpと同じことをする。
本当は無いが、面倒なのでmultipleとdivideという命令を追加し、それぞれ掛ける、割る の命令とした。

f:id:AkaGhef:20200715222648j:image

最後まで見て頂きありがとうございますm(*_ _)m

記事は2週間前に完成してたのですが、アップロードエラーを吐かれてやる気を失って遅くなりました。

暫定的ではありますが、高3の身分ゆえ冠模試があるので受験勉強に集中したいと思いますまる

sin計算機の解説も未定です。。。

それでは〜〜