標準ＴＴＬだけ（！）でCPUをつくろう！（組立てキットです！）
(ホントは７４ＨＣ、ＣＭＯＳなんだけど…）
［第６５９回］
●ルート計算の仕組み
このところ、ＴＫ－８０用に書かれたルート計算プログラムについて説明をしております。
ＮＤ８０ＺⅢ組立キットをご購入いただいた北海道のＭ様から、ＴＫ－８０応用プログラムとして送っていただいたプログラムです。
０１～９９の範囲の整数のみですが、ルート（平方根）を求めるプログラムです。
１９７７年当時の雑誌「マイコン」に載っていた記事をもとに、Ｍ様がＬＥＤ表示部分に改良を加えられたものだということです。
私は倍精度の浮動小数点演算機能をもつＺＢ３ＢＡＳＩＣを作りましたのでＺ８０でルートの計算をさせるプログラムも書くことができます（といいましても、もうずいぶん昔に作ったものですから、ほとんど記憶にありませんが）。
浮動小数点の演算は２進数で行ないますし、かなり複雑なサブルーチン群から構成されています。
当然のことながら、ハンドアセンブルでできるような代物ではありません。アセンブラが必須になります。
ですから、Ｍ様からプログラムをメール添付で送っていただいたとき、その余りの短さに、驚きましたし、大いに疑問でもありました。
たとえ最大２桁の整数に対する平方根に限る、という制約付きであったとしても、これは余りに短すぎます。
ちょっと信じられない気持ちでした。
いったいどうやって計算をしているのだろう、と興味津々で、お送りいただいたプログラムを解析してみることにいたしました。
お送りいただいたのはマシン語のバイナリファイルでしたから、そのままではなかなか解読することが困難です。
そこでＮＤ８０ＺⅢ組立キットに含まれている、Ｚ８０逆アセンブラ、Ｚ８０アセンブラなどのツールを使って、ルート計算プログラムを理解しやすい形に編集しなおしました。
というところまでが、前回までのお話です。
今回はいよいよ、そのルート計算の秘密にせまります。
（なんだか某番組のキメセリフのようです）
ルートの計算を行なっているのはプログラムの、以下の部分です。
信じられないほど簡単です。
;
;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/
なるほど！納得です。
２０１０．１１．１２ｕｐｌｏａｄ
前へ
次へ
ホームページトップへ戻る