ワンボードマイコンをつくろう！（パソコンの原点はここから始まった）
ＴＫ８０ソフトコンパチブル！８０８０、Ｚ８０マシン語からＢＡＳＩＣまでこれ１台でこなせます
当記事は２００９年１１月から「ＴＴＬでＣＰＵをつくろう！」というタイトルの もとにほとんど毎日連載をしてきたものを再編集したものです。 ２０１１．７．７
前へ
次へ
目次へ戻る
ホームページトップへ戻る
☆ルート計算プログラム
ＮＤ８０ＺⅢをご購入いただいたお客様からＴＫ－８０応用プログラムを送っていただきました。
プログラムを解析する過程でＮＤ８０ＺⅢ組立キットに附属しているＺ８０アセンブラ、Ｚ８０逆アセンブラを使います。それらのプログラムの使用例としても参考になると思います。

［第１１８回］

●ルート計算の仕組み

このところ、ＴＫ－８０用に書かれたルート計算プログラムについて説明をしております。
ＮＤ８０ＺⅢ組立キットをご購入いただいた北海道のＭ様から、ＴＫ－８０応用プログラムとして送っていただいたプログラムです。
０１～９９の範囲の整数のみですが、ルート（平方根）を求めるプログラムです。
１９７７年当時の雑誌「マイコン」に載っていた記事をもとに、Ｍ様がＬＥＤ表示部分に改良を加えられたものだということです。

私は倍精度の浮動小数点演算機能をもつＺＢ３ＢＡＳＩＣを作りましたのでＺ８０でルートの計算をさせるプログラムも書くことができます（といいましても、もうずいぶん昔に作ったものですから、ほとんど記憶にありませんが）。
浮動小数点の演算は２進数で行ないますし、かなり複雑なサブルーチン群から構成されています。
当然のことながら、ハンドアセンブルでできるような代物ではありません。アセンブラが必須になります。

ですから、Ｍ様からプログラムをメール添付で送っていただいたとき、その余りの短さに、驚きましたし、大いに疑問でもありました。
たとえ最大２桁の整数に対する平方根に限る、という制約付きであったとしても、これは余りに短すぎます。
ちょっと信じられない気持ちでした。
いったいどうやって計算をしているのだろう、と興味津々で、お送りいただいたプログラムを解析してみることにいたしました。

お送りいただいたのはマシン語のバイナリファイルでしたから、そのままではなかなか解読することが困難です。
そこでＮＤ８０ＺⅢ組立キットに含まれている、Ｚ８０逆アセンブラ、Ｚ８０アセンブラなどのツールを使って、ルート計算プログラムを理解しやすい形に編集しなおしました。
というところまでが、前回までのお話です。

今回はいよいよ、そのルート計算の秘密にせまります。
（なんだか某番組のキメセリフのようです）

ルートの計算を行なっているのはプログラムの、以下の部分です。
信じられないほど簡単です。

              ;
              ;KEISAN START
              ;
8023 3E01           LD A,01
8025 32B382         LD (HIKUSU78),A
8028 CD7080   KEISAN_LOOP:CALL HIKIZAN
802B DA3780         JP C,KEISAN_END
802E CD8480         CALL KOTAE_ADD1
8031 CD9380         CALL HIKUSUADD2
8034 C32880         JP KEISAN_LOOP

よく見ますと３つのサブルーチンをＣＡＬＬしています。
ＨＩＫＩＺＡＮとＫＯＴＡＥ＿ＡＤＤ１とＨＩＫＵＳＵＡＤＤ２です。
最後のＨＩＫＵＳＵＡＤＤ２は前回まで複数回にわたって説明をしてきました。

まずはそれぞれのサブルーチンを示したうえで説明をすることにいたします。
最初はＨＩＫＩＺＡＮです。

              ;
              ;TISU=TISU-HIKUSU
              ;
8070 21B382   HIKIZAN:LD HL,HIKUSU78
8073 11AF82         LD DE,TISU78
8076 0604           LD B,04
8078 AF             XOR A
8079 1A       HIKIZAN_2:LD A,(DE)
807A 9E             SBC A,(HL)
807B 27             DAA
807C 12             LD (DE),A
807D 2B             DEC HL
807E 1B             DEC DE
807F 05             DEC B
8080 C27980         JP NZ,HIKIZAN_2
8083 C9             RET

その名の通り、置数から引く数を減算するサブルーチンです。
置数（ＴＩＳＵ１２～ＴＩＳＵ７８）、引く数（ＨＩＫＵＳＵ１２～ＨＩＫＵＳＵ７８）と答え（ＫＯＴＡＥ１２、ＫＯＴＡＥ３４）は、ＲＡＭ上に置かれており、連続したアドレスに配置されていますが、それを下図のように並べると理解しやすくなります。

各レジスタの値は、置数を０２としてスタートしたときの計算開始直前の値です。
これから２の平方根を求めようとしています。
置数は００～９９の整数２桁の範囲の数で、上の図のように、十進８桁のレジスタの上位２桁に置きます。
下位６桁は全て０が置かれます。
引く数は図のように初期値１からスタートします。ここも十進８桁です。
計算結果は答え（ＫＯＴＡＥ）に十進４桁で入れられます。
計算は１バイトを２桁の十進数で示すＢＣＤ（２進化十進）数として行なわれます。
ＢＣＤ数についてはＣＰＵをつくろう！［第１０回］で説明をしております。
計算は全て十進数の整数として行なわれます。
ＨＩＫＩＺＡＮサブルーチンでは、上図例の場合、
２００００００－１の計算が行なわれますが、実際には２００００００ではなくて２なのですから、２．００００００－０．０００００１の計算をしていることになります。
しかし固定小数点の計算ですから、小数点を取ってしまって、整数同士の計算と考えても構いません。
ついでに答え（ＫＯＴＡＥ）は整数４桁で求められますが、ここは実際には、０．０００の位置に小数点があるのですが、それが省略されていると考えてください。
そのように、ＨＩＫＩＺＡＮサブルーチンはＴＩＳＵからＨＩＫＵＳＵを引いて、その結果をＴＩＳＵに入れます。

次はＫＯＴＡＥ＿ＡＤＤ１サブルーチンです。

              ;
              ;KOTAE_ADD1
              ;
8084 21B582   KOTAE_ADD1:LD HL,KOTAE34
8087 7E             LD A,(HL)
8088 C601           ADD A,01
808A 27             DAA
808B 77             LD (HL),A
808C 2B             DEC HL
808D 7E             LD A,(HL)
808E CE00           ADC A,00
8090 27             DAA
8091 77             LD (HL),A
8092 C9             RET

これも簡単なプログラムです。
ＨＩＫＩＺＡＮサブルーチンが１回実行される度に、答え（ＫＯＴＡＥ）レジスタの値を＋１します。
つまり答えは、引き算をした回数と同じことになります。
え？
平方根が、引き算をした回数と同じ？
それはまたどういうことでしょう？
ちょっと信じられません。

カギはＨＩＫＵＳＵＡＤＤ２サブルーチンにあります。

              ;
              ; HIKUSU=HIKUSU+2
              ;
8093 0603     HIKUSUADD2:LD B,03
8095 21B382         LD HL,HIKUSU78
8098 7E             LD A,(HL)
8099 C602           ADD A,02
809B 27             DAA
809C 77             LD (HL),A
809D 2B       HIKUSUADD2_2:DEC HL
809E 7E             LD A,(HL)
809F CE00           ADC A,00
80A1 27             DAA
80A2 77             LD (HL),A
80A3 05             DEC B
80A4 C29D80         JP NZ,HIKUSUADD2_2
80A7 C9             RET

このサブルーチンは引く数（ＨＩＫＵＳＵ）レジスタの値に２を加えます。
ただそれだけです。
このＨＩＫＵＳＵＡＤＤ２サブルーチンも、ＨＩＫＩＺＡＮサブルーチンが１回実行されたあとに、同じように１回実行されます。

すると、一体どういう計算をしていることになるでしょうか。
最初に０２００００００－１＝０１９９９９９９が計算され、そしてＫＯＴＡＥは０＋１＝１になり、そしてＨＩＫＵＳＵは１＋２＝３になります。
それで１回の計算が終わりました。
次は、ＴＩＳＵは０１９９９９９９－３＝０１９９９９９６、ＫＯＴＡＥは１＋１＝２、ＨＩＫＵＳＵは３＋２＝５になります。
その次は、ＴＩＳＵは０１９９９９９６－５＝０１９９９９９１、ＫＯＴＡＥは２＋１＝３、ＨＩＫＵＳＵは５＋２＝７になります。
そのようにどんどん計算していって、最後にＴＩＳＵからＨＩＫＵＳＵが引けなくなったら、計算終了で、そのときにＫＯＴＡＥは２の平方根になっている、というのですけれど…。

ううう。
ほんまかいなあ？
まるで手品を見せられているようです。

む？
でも、まてよ？
すると、引く数は、１、３、５、７、９…という数列になるのでは？
むむ。なんだかはるか遠い昔に数学の試験に出てきたような…？
そして、答えの平方根というのが、引き算をした回数ということは…。
それは、つまり、１、３、５、７、９…の数列の要素の数と同じでは？

おお、ひょっとすると、それならば…。
今、求める答えである平方根、つまり引き算の回数をＮとすると、それは１、３、５、７、９…の数列の要素の数と一致します。
ＴＩＳＵから、引ききれなくなるまで、その数列を順に引いていくのですから、その数列の総和はＴＩＳＵと等しいと考えることができます（端数、つまり余りは切り捨てです）。
ではＮ個の要素からなる数列１、３、５、…、２Ｎ－１の総和はいくつになるでしょうか？
これ。昔は小学校の算数で習ったんですよねえ。
勿論Ｎなんて出てきませんし、１、２、３、…、１０くらいのものでしたけど。
（初めの数＋終わりの数）×個数÷２
思い出しませんか？
つまり総和Ｓ＝（１＋２Ｎ－１）×Ｎ／２
ですからＳ＝Ｎ２

あれま。こんなところに２乗が出て来てしまいました。
数列の総和Ｓは置数と同じ、ということでしたから、おお、確かに、Ｎは置数Ｓの平方根になるじゃありませんか！

いやあ、これはすごい。
最初にどなたがこういうことを思いつかれたのでしょう。
私はプログラムを解析することによって、そのように計算すればよい、という結論にたどりついたわけですけれど、こりゃあちょっと思いつきませんよねえ。

そうしましたら、Ｍ様からこんなページをご紹介いただきました。
http://www.wizforest.com/gear/tiger/sqrt/

なるほど！納得です。
ＣＰＵをつくろう！第６５９回（２０１０．１１．１２ｕｐｌｏａｄ）を再編集

ワンボードマイコンをつくろう！［第１１８回］
２０１１．７．７ｕｐｌｏａｄ

前へ
次へ
目次へ戻る
ホームページトップへ戻る