2009年1月22日木曜日

開平法

手回し計算機は十進である. 二進でも事情は変らない. むしろ簡単といえる.

1000000000 (2^9=512) を筆算で開平する手順は以下のとおり.



左部分は2x+yを作っているから, 最後の平方根はkの行の左部分の半分, 10110(=22)で, 剰余はkの行の中部分の 11100(=28) である. つまり22*22+28=512である.

これをプログラムに書き直したのは, 以下のとおり. 途中経過を印字する行はいらない.


(define (sqrt n)
(define (ss n s) (if (> (* s 4) n) s (ss n (* s 4))))
(define (sq n q s)
(display (list 'n n 'q q 's s)) (newline)
(if (> s 0)
(let ((a (+ q s)))
(if (>= n a) (sq (- n a) (+ (/ q 2) s) (quotient s 4))
(sq n (/ q 2) (quotient s 4))))
(cons q n)))
(sq n 0 (ss n 1)))


下請け関数 sq の引数 n は部分剰余, q は 部分平方根, s は計算中の位置を記憶するストロブである. 各ステップで, 部分剰余と比較する数 a を作り, 引けるなら部分剰余は n-a になり, 次の部分平方根とストロブを作る. 引けなければ部分剰余はそのまま, 平方根は1桁右にずれるだけである.

もう1つの下請け関数 ss は, 1から4倍を繰り返し, n と比較しながら最初のストロブの位置を決める.

512を開平した時, n, q, sの状態は次のとおり.


(sqrt 512)
(n 512 q 0 s 256)
(n 256 q 256 s 64)
(n 256 q 128 s 16)
(n 112 q 80 s 4)
(n 28 q 44 s 1)
(n 28 q 22 s 0)
=> (22 . 28)



以前のブログに書いた個人用電卓 Happy Hacking Calculatorの開平は, 基本的にこの方法を採用している.


ところで, これまでの二進の開平では, 引けるかどうかを見て, 引ければ引くという方法であった. これに対し二進の開平では, 引放し開平が出来る. つまり引きすぎて部分剰余が負になったら, 足し戻さず, 次のステップでは足すのである. 理屈は面倒なので書かないが, 512をこの方法で開平する様子を示す.



この方法ではまずストロブの位置から1を引く. 部分剰余が正なら, 部分平方根の最後に101をつけたものを引く. 負なら, 011をつけたものを足す. 平方根は最初の無条件の減算を除き, 引いたときは1, 足した時は0として作る.最後の桁を1として追加する. 従ってこの方法では, 平方根は必ず奇数になり, 剰余も正だったり負だったりする.

512を開平すると, 引く, 足す, 引く, 引くとやったので, 1011となり, 最後に1を追加して, 10111 (=23)が得られる. 剰余は -17 である. 23*23-17=512になっている.

平方根が q, 剰余が r で負の時は, 平方根が奇数なので最後の1を0に変る. つまり平方根を q-1にする. 平方根が q の時, 剰余が r なので, 新しい剰余を r' とするとq*q+r=n=(q-1)*(q-1)+r' だからr'=r+2(q-1)+1 とすればよい. 上の例では, 23から1引いた22が平方根, その剰余は-17+2*22+1=28 と得られる.

0 件のコメント: