もとにほとんど毎日連載をしてきたものを再編集したものです。2011.7.7前へ次へ目次へ戻るホームページトップへ戻る☆ルート計算プログラムND80Z�Vをご購入いただいたお客様からTK−80応用プログラムを送っていただきました。プログラムを解析する過程でND80Z�V組立キットに附属しているZ80アセンブラ、Z80逆アセンブラを使います。それらのプログラムの使用例としても参考になると思います。[第118回]●ルート計算の仕組みこのところ、TK−80用に書かれたルート計算プログラムについて説明をしております。ND80Z�V組立キットをご購入いただいた北海道のM様から、TK−80応用プログラムとして送っていただいたプログラムです。01〜99の範囲の整数のみですが、ルート(平方根)を求めるプログラムです。1977年当時の雑誌「マイコン」に載っていた記事をもとに、M様がLED表示部分に改良を加えられたものだということです。もつZB3BASICを作りましたのでZ80でルートの計算をさせるプログラムも書くことができます(といいましても、もうずいぶん昔に作ったものですから、ほとんど記憶にありませんが)。浮動小数点の演算は2進数で行ないますし、かなり複雑なサブルーチン群から構成されています。当然のことながら、ハンドアセンブルでできるような代物ではありません。アセンブラが必須になります。M様からプログラムをメール添付で送っていただいたとき、その余りの短さに、驚きましたし、大いに疑問でもありました。最大2桁の整数に対する平方根に限る、という制約付きであったとしても、これは余りに短すぎます。信じられない気持ちでした。やって計算をしているのだろう、と興味津々で、お送りいただいたプログラムを解析してみることにいたしました。お送りいただいたのはマシン語のバイナリファイルでしたから、そのままではなかなか解読することが困難です。そこでND80Z�V組立キットに含まれている、Z80逆アセンブラ、Z80アセンブラなどのツールを使って、ルート計算プログラムを理解しやすい形に編集しなおしました。いうところまでが、前回までのお話です。今回はいよいよ、そのルート計算の秘密にせまります。(なんだか某番組のキメセリフのようです)ルートの計算を行なっているのはプログラムの、以下の部分です。信じられないほど簡単です。KEISAN_LOOPよく見ますと3つのサブルーチンをCALLしています。HIKIZANとKOTAE_ADD1とHIKUSUADD2です。最後のHIKUSUADD2は前回まで複数回にわたって説明をしてきました。それぞれのサブルーチンを示したうえで説明をすることにいたします。最初はHIKIZANです。RETその名の通り、置数から引く数を減算するサブルーチンです。置数(TISU12〜TISU78)、引く数(HIKUSU12〜HIKUSU78)と答え(KOTAE12、KOTAE34)は、RAM上に置かれており、連続したアドレスに配置されていますが、それを下図のように並べると理解しやすくなります。各レジスタの値は、置数を02としてスタートしたときの計算開始直前の値です。これから2の平方根を求めようとしています。置数は00〜99の整数2桁の範囲の数で、上の図のように、十進8桁のレジスタの上位2桁に置きます。下位6桁は全て0が置かれます。引く数は図のように初期値1からスタートします。計算結果は答え(KOTAE)に十進4桁で入れられます。計算は1バイトを2桁の十進数で示すBCD(2進化十進)数として行なわれます。BCD数についてはCPUをつくろう![第10回]で説明をしております。計算は全て十進数の整数として行なわれます。HIKIZANサブルーチンでは、上図例の場合、2000000−1の計算が行なわれますが、実際には2000000ではなくて2なのですから、2.000000−0.000001の計算をしていることになります。固定小数点の計算ですから、小数点を取ってしまって、整数同士の計算と考えても構いません。ついでに答え(KOTAE)は整数4桁で求められますが、ここは実際には、0.000の位置に小数点があるのですが、それが省略されていると考えてください。そのように、HIKIZANサブルーチンはTISUからHIKUSUを引いて、その結果をTISUに入れます。次はKOTAE_ADD1サブルーチンです。RETこれも簡単なプログラムです。HIKIZANサブルーチンが1回実行される度に、答え(KOTAE)レジスタの値を+1します。答えは、引き算をした回数と同じことになります。え?平方根が、引き算をした回数と同じ?それはまたどういうことでしょう?ちょっと信じられません。カギはHIKUSUADD2サブルーチンにあります。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=N2あれま。こんなところに2乗が出て来てしまいました。数列の総和Sは置数と同じ、ということでしたから、おお、確かに、Nは置数Sの平方根になるじゃありませんか!いやあ、これはすごい。最初にどなたがこういうことを思いつかれたのでしょう。私はプログラムを解析することによって、そのように計算すればよい、という結論にたどりついたわけですけれど、こりゃあちょっと思いつきませんよねえ。しましたら、M様からこんなページをご紹介いただきました。http://www.wizforest.com/gear/tiger/sqrt/なるほど!納得です。CPUをつくろう!第659回(2010.11.12upload)を再編集ワンボードマイコンをつくろう![第118回]2011.7.7upload前へ次へ目次へ戻るホームページトップへ戻る。