標準TTLだけ(!)でCPUをつくろう!(組立てキットです!)
(ホントは74HC、CMOSなんだけど…)
[第659回]

●ルート計算の仕組み

このところ、TK−80用に書かれたルート計算プログラムについて説明をしております。
ND80ZV組立キットをご購入いただいた北海道のM様から、TK−80応用プログラムとして送っていただいたプログラムです。
01〜99の範囲の整数のみですが、ルート(平方根)を求めるプログラムです。
1977年当時の雑誌「マイコン」に載っていた記事をもとに、M様がLED表示部分に改良を加えられたものだということです。

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

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

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

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

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

              ;
              ;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


よく見ますと3つのサブルーチンをCALLしています。
HIKIZANとKOTAE_ADD1とHIKUSUADD2です。
最後のHIKUSUADD2は前回まで複数回にわたって説明をしてきました。

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

              ;
              ;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

その名の通り、置数から引く数を減算するサブルーチンです。
置数(TISU12〜TISU78)、引く数(HIKUSU12〜HIKUSU78)と答え(KOTAE12、KOTAE34)は、RAM上に置かれており、連続したアドレスに配置されていますが、それを下図のように並べると理解しやすくなります。

各レジスタの値は、置数を02としてスタートしたときの計算開始直前の値です。
これから2の平方根を求めようとしています。
置数は00〜99の整数2桁の範囲の数で、上の図のように、十進8桁のレジスタの上位2桁に置きます。
下位6桁は全て0が置かれます。
引く数は図のように初期値1からスタートします。ここも十進8桁です。
計算結果は答え(KOTAE)に十進4桁で入れられます。
計算は1バイトを2桁の十進数で示すBCD(2進化十進)数として行なわれます。
BCD数については[第10回]で説明をしております。
計算は全て十進数の整数として行なわれます。
HIKIZANサブルーチンでは、上図例の場合、
2000000−1の計算が行なわれますが、実際には2000000ではなくて2なのですから、2.000000−0.000001の計算をしていることになります。
しかし固定小数点の計算ですから、小数点を取ってしまって、整数同士の計算と考えても構いません。
ついでに答え(KOTAE)は整数4桁で求められますが、ここは実際には、0.000の位置に小数点があるのですが、それが省略されていると考えてください。
そのように、HIKIZANサブルーチンはTISUからHIKUSUを引いて、その結果をTISUに入れます。


次はKOTAE_ADD1サブルーチンです。

              ;
              ;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


これも簡単なプログラムです。
HIKIZANサブルーチンが1回実行される度に、答え(KOTAE)レジスタの値を+1します。
つまり答えは、引き算をした回数と同じことになります。
え?
平方根が、引き算をした回数と同じ?
それはまたどういうことでしょう?
ちょっと信じられません。

カギはHIKUSUADD2サブルーチンにあります。

              ;
              ; 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

このサブルーチンは引く数(HIKUSU)レジスタの値に2を加えます。
ただそれだけです。
このHIKUSUADD2サブルーチンも、HIKIZANサブルーチンが1回実行されたあとに、同じように1回実行されます。

すると、一体どういう計算をしていることになるでしょうか。
最初に02000000−1=01999999が計算され、そしてKOTAEは0+1=1になり、そしてHIKUSUは1+2=3になります。
それで1回の計算が終わりました。
次は、TISUは01999999−3=01999996、KOTAEは1+1=2、HIKUSUは3+2=5になります。
その次は、TISUは01999996−5=01999991、KOTAEは2+1=3、HIKUSUは5+2=7になります。
そのようにどんどん計算していって、最後にTISUからHIKUSUが引けなくなったら、計算終了で、そのときにKOTAEは2の平方根になっている、というのですけれど…。

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

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

おお、ひょっとすると、それならば…。
今、求める答えである平方根、つまり引き算の回数をNとすると、それは1、3、5、7、9…の数列の要素の数と一致します。
TISUから、引ききれなくなるまで、その数列を順に引いていくのですから、その数列の総和はTISUと等しいと考えることができます(端数、つまり余りは切り捨てです)。
ではN個の要素からなる数列1、3、5、…、2N−1の総和はいくつになるでしょうか?
これ。昔は小学校の算数で習ったんですよねえ。
勿論Nなんて出てきませんし、1、2、3、…、10くらいのものでしたけど。
(初めの数+終わりの数)×個数÷2
思い出しませんか?
つまり総和S=(1+2N−1)×N/2
ですからS=N

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

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

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

なるほど!納得です。
2010.11.12upload

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