2014年1月14日火曜日

開平法

CurtaのウェブページにDibble-Dabble法という平方根の アルゴリズムがあった.
 2. Dibble-dabble method

2.A Shift the carriage full CCW and zeroize.

2.B Enter "1" in the most significant input slider (IS).

2.C Add ONCE. If the value in the total register exceeds the 
target number, then subtract out the last number added and go 
to step F.

2.D Increase the value in the currently active IS by mentally 
adding "2". If adding "2" to "9" change the "9" to "1" and 
add "1" the the next left input slider (not relevant first 
time through).

2.E Repeat steps C & D.

2.F Reduce the setting of the current IS by "1" and shift the 
carriage CW one step. If the limit of carriage travel is 
reached, go to step I.

2.G Enter "1" in the next most significant IS (the one to the 
right of the one previously used).

2.H Repeat steps C through G.

2.I The number in the "turns counter" register is the true 
square root.
やってみよう. その前に日本語にすると

2.A キャリージを反時計回り(counter clock wise)に一杯に 回し, 零にする(zeroize).

2.B 置数レジスタ(input slider)の最上位に1を置く. 2.C 一度加算する. 結果レジスタ(total register)の値が, 目標の数値を越えるなら, 最後に足した数を引き, Fへ進む.

2.D 置数レジスタを2増やす. 2を9に足す時は, 9を1にし, 置数レジスタの左の 桁に1足す.

2.E CとDのステップを繰り返す.

2.F 置数レジスタの値を1減らし, キャリージを時計回りに1ステップ回す. キャリージ が回らないならIへ進む.

2.G 置数レジスタの次の最上位(前回の桁の右の桁)に1を置く.

2.H CからGのステップを繰り返す.

2.I 回転レジスタの数が平方根になる.

ここに Curtaの精巧なシミュレータがあるからそれを使って2の平方根を求めてみよう.

Curta計算機の部分の名称は下の図を参照してほしい.



Curtaの操作の基本は次の通り.

加減する数は左の絵の下の置数レジスタにつまみを上下して入れる.

加減算の結果は右の絵の結果レジスタに出る. レジスタへの加減する位置は キャリージを回して決める. それにはキャリージの左右の矢印をクリックする.

減算の時は左の絵の上の操作ハンドルを上に引き上げ, 加算の時は 押し下げ, 右の絵の操作ハンドルを回す.

結果レジスタや回転レジスタは右の絵のクリアレバーを回す.

そこで2の平方根を小数点以下5桁求めるために20000000000の平方根を 計算する. (下の説明の行末の番号は後のトレースの行番号.)

まずキャリージの右の矢印を5回押してキャリージを回す.

置数レジスタの6の桁を1にして加算する. 
結果レジスタは10000000000, 回転レジスタは100000になる. (1)
置数レジスタの6の桁を3にして加算する. 
結果レジスタは40000000000, 回転レジスタは200000になる. (2)
40000000000は20000000000より大きいから減算する. (3)
6の桁を1減らして2にし, キャリージを1桁戻す.

置数レジスタの5の桁を1にして(置数レジスタは210000になる)加算
する.(4)
結果レジスタは12100000000, 回転レジスタは110000になる.
置数レジスタの5の桁を3にして加算する. 5にして, 7にして, 9にし
て加算する.
結果レジスタは22500000000, 回転レジスタは150000になる.(8)
20000000000より大きいから減算する.(9)
5の桁を1減らして8にし, キャリージを1桁戻す.

置数レジスタの4の桁を1にして(置数レジスタは281000になる)加算す
る.(10)
3にして加算する.(11)
結果レジスタは20164000000, 回転レジスタは142000になる.
20000000000より大きいから減算する.(12)
4の桁を1減らして2にし, キャリージを1桁戻す.

置数レジスタの3の桁を1にして(置数レジスタは282100になる)加算す
る.
9まで加算すると(17)
結果レジスタは20022250000, 回転レジスタは141500になる.

20000000000より大きいから減算する.(18)
3の桁を1減らして8にし, キャリージを1桁戻す.
この辺までで大体分かったからプログラムを書いてみる.
(define (dibbledabble radicand)
 (let ((s0 1) (s1 1) (s 0) (a 0) (c 0))
  (define (loopp) (display "+") (display s) (display " ")
   (set! a (+ a s)) (set! c (+ c s1)) (display a)
   (display " ") (display c) (newline)
   (if (> a radicand)
    (begin (display "-") (display s) (display " ") 
     (set! a (- a s)) (set! c (- c s1)) (display a)
     (display " ") (display c) (newline)
     (set! s (/ (- s s0) 10))
     (if (> s0 1)
      (begin (set! s0 (/ s0 100)) (set! s1 (/ s1 10)) 
       (set! s (+ s s0)) (loopp)) c))
    (begin (set! s (+ s s0 s0)) (loopp))))
  (do ((n 100 (* n 100))) ((> n radicand))
   (set! s0 (* s0 100)) (set! s1 (* s1 10)))
  (display radicand) (display " ") (display s0)
  (display " ") (display s1) (newline) (set! s s0)
  (loopp)))

(dibbledabble 20000000000)
上のプログラムでletで用意したs0は置数レジスタを増減する数, s1は回転 カウンタを増減する数, sは結果レジスタに加減する数, aは結果レジスタ, cは回転カウンタ, radicandは平方根をとる数である.

radicandを20000000000とした時, まずs0とs1を用意する. それが本体の do loopである. s0は10000000000, s1は100000になる.

上の方のloopが1桁分の計算で, aにsを, cにs1を足す. (if (> a radicand) は結果レジスタが目標を超えた場合で, 置数レジスタと回転レジスタを 戻し, sからも1引いてキャリージを回すように1/10にする. またs0を1/100, s1を1/10にする.

超えない時はsにs0を2回足して加算を繰り返す.

このプログラムを実行した結果が次だ. 左端の斜体の行番号は後から追加した. 0行目はtarget, s0, s1を示す. 後の行はsを足したか引いたかを+, -で示し, s, a, cを順に示している.
0 20000000000 10000000000 100000
1+10000000000 10000000000 100000
2+30000000000 40000000000 200000
3-30000000000 10000000000 100000
4+2100000000 12100000000 110000
5+2300000000 14400000000 120000
6+2500000000 16900000000 130000
7+2700000000 19600000000 140000
8+2900000000 22500000000 150000
9-2900000000 19600000000 140000
10+281000000 19881000000 141000
11+283000000 20164000000 142000
12-283000000 19881000000 141000
13+28210000 19909210000 141100
14+28230000 19937440000 141200
15+28250000 19965690000 141300
16+28270000 19993960000 141400
17+28290000 20022250000 141500
18-28290000 19993960000 141400
19+2828100 19996788100 141410
20+2828300 19999616400 141420
21+2828500 20002444900 141430
22-2828500 19999616400 141420
23+282841 19999899241 141421
24+282843 20000182084 141422
25-282843 19999899241 141421
この1, 3, 5,...と引くのは要するに手回しの機械式計算機の平方根の計算法で あって, それがdibble-dabbleという名前だとは知らなかった. 以前のブログの 5倍してから5, 15, 25,...と引くのは電動計算機の方法というべきであったかも しれない.