2009年1月23日金曜日

開平法

江戸時代の和算の書, 塵劫記を岩波文庫で読んでいたら, 開平法の項があった. 「開平法を商実法により除之事」というタイトルである. 開平法は平方根をとること, 商実法はそれぞれそういう名称の3つの算盤である. これを除すること とは開平も除算の一種と思われていたからであろう. 商には除算の商と同じで, 平方根が得られる. 実には部分剰余を置く. 法には実から引く数を置く. 何々を法として...というのと同じだ. そう考えると, 和算用語はまだわれわれの周辺に存在していると気づく.

塵劫記では, 解法はすべて実例によるから, 「ここに15129坪有り. これを四方になしては, なにほどに成るぞといふ時に, 123間四方.」のような記述だ.

彼らはなにをやったか見てみよう. 下図参照. われわれの筆算での例も示す. 以下の(a), (b), (c)は下図のa, b, cに対応する.

(a) 「実に15129坪と置き, まず位を見る. 一十百, 一十百とかずへて, あがりたる時, 百と二度あたらば, 百の位と定め,」と始まる. 文頭の「実に」はindeedではなく, 「実という算盤に」の意である. 最上位が100の自乗の位置であることを見つける. 「商に百と置き, 扨, 下法にて, 百より又一十百とあがりて, 百と置き,」



4つ目の算盤は「下法」という名で(塵劫記には「下方」と書いてあったりする), いまは2桁左へシフトしてある. (算盤がずらして置いてある.) 商と下法に百と置くのである. 百の桁に置くのは分かるが, 平方根のその桁をどうして1と決めたかは書いてない.

「この上の法にて, 下法の百, 商の百をよぶ時, 1万坪と成り, 実で除之. 実に残りて5129坪有り.」

下法の百, 商の百を「よぶ」とは, 掛けることと思われる. 上の法にてだから, それを法に置き, 実から引くわけである. (ここでの「除く」は「引く」) 図中の入れ子の正方形の濃い正方形を引いたことになる. 筆算と比べれば, 左部分の a の行が下法, 中部分の a が実, 中部分の b が法である.


(b) 「商の百の次に2十と置く. さて, 下法をば, 1位下げて, 百を1倍して2百と置き, この下に又2十と置く. 」 昔の1倍は今の2倍のことらしい. 商に2十を置いたのは, 平方根の次の桁が決ったのである. この決り方も理由は不明. 百を1倍しで, 筆算の c の行の左の 2 が出来たことになる. 図でいえば1辺100の(下と左の)2辺分が出来た. 又2十を置くは, 正方形の図の薄い部分を引く準備で, 左下の薄い正方形の1辺を足した. 220に20を掛ければ, この部分の面積が得られる.

「さて, 法にて, 下法の2百に商の2十をよぶ. 22の4千, 22の4百, 此の4千4百を実にて引くべし.」 下法の200は220の誤りである. それに20を掛けて引く.

「実に, 残りて729坪有り.」

(c) 「商に, 2十の次に3と置く. 下法をば1位をさげて, 2十を1倍して4十と置く.」 これで e の 24 が出来た. 「此の下に又3と置く. さて, 法にて, 商の3をもって下法によぶ. 23の6百, 34の百2十, 33の9と置くとき, 法に729坪有り. これを実にて引きはらふ也. さて, 商を見れば, 123間四方に成る也.」

大体は分かるが, 平方根の桁に何が立つかの判定は勘によるのだろうか.


塵劫記には開立法, つまり立方根の求め方も書いてあった. 「坪数1728坪有り. これをたて, よこ, たかさ, おなじたけにしてなにほどぞといふ時に, 12間六方也.」私もまだこの開立法の解読はしていないが, この1728が12の3乗なことは覚えている人も多かろう. ところで坪は平方間と思っていたが, 立方間も坪というのかな.

9の3乗=729も覚えている人に:
「彼(Ramanujan)がパトニーで療養していた時, 見舞いにいったのを(Hardyは)覚えている. 1729番というタクシーに乗ったので, その数には何の面白味もないといい, それが悪い予兆でないことを望むといった. 『いや』彼は答えた『それは非常に興味のある数だ. それは二通りで二つの立方数の和で表現出来る最小の数だ』」 (計算機プログラムの構造と解釈 第二版 203ページ 脚注70) 1729=123+13=103+93だから, Ramanujanでなくても知っていた人はいたに違いない.

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 と得られる.

2009年1月21日水曜日

開平法

手回し計算機で開平するには, 手回し計算機のことも説明する必要があろう.

1950年頃からリヒテンシュタインで製造されていた, Curtaという小さい機械式の計算機があった. 設計したのはCurt Herzstarkで, 第二次世界大戦中, ドイツ軍に抑留されていたときに設計したといわれている.

サーチエンジンでCurta Calculatorを探すとサイトがいくつも見つかるが, 精巧なシミュレータはここ, マニュアルはここにある.

シミュレータの説明用に私が描いたCurtaの絵は下の通り.






上が正面図, 中が平面図である. 下は説明用の図(表?)だ.

Curtaは筒状で, 正面下側に8桁のSetting Registerがあり, 赤で示すノブを下げると0から9までの各桁の値が設定できる. シミュレータでは同時に下の表のSETTING DIALにも値が入る. Operation HandleをZero Positionから時計方向に1回転(平面図でHandle から下に出ている矢印をクリック)すると, この値がResult Dialに足される. HandleはZero Positionまで回す.

Curtaの上方には, 左右に5桁分回転できるCarriageがあり, 平面図ではこれが見えている. Carriageの上面には, 11桁のResult Dialと6桁のRevolution Counterがある. Carriageがこの図の位置なら, Setting Registerの値は, Result Dialの最下位に足される. 正面図のCarriageの右の赤い矢印をクリックすると, 平面図のCarriageは反時計方向に1桁分回転し, その位置では下から2桁目に足される.

Operation Handleを1回転すると, Setting Dialの最下位に対応するRevolution Counterに1足される. 従ってSetting Dialに34を置き, Carriageの最初の位置でHandleを6回転し, Carriageを1桁回し, 3回転すると, Result Dialには34*36=1224が入り, Revolution Counterには36が入る.

平面図で11時の方向に出ている輪のようなものは, Clearing Leverで, Revolution CounterとResult Dialの境界に止まり, どちらかに回転すると, そのCounterやDialがリセットされる.

Curtaの正面図で, Setting Registerの右に見えるReversion Leverは, ノブが図の位置では, Handleの回転でRevolution Counterに1足され, ノブを下に下げると, Counterから1引かれる.

Curtaの特色の1つは, 補数計算をするので, 減算でもOperation Handleを加算と同様に時計方向に回すことだ. ただしOperation Handleに右にある上向き矢印をクリックし, 回転軸を上に少し引き抜く. 加算に戻すには, 減算時に下向きになっていた矢印をクリックして, 回転軸を押し下げる.

除算の時は, 被除数をResult Dialに, 除数をSetting Dialにセットし, Reversion Leverを下位置にし, 回転軸を引き抜き, 各桁で引けなくなるまで回転し, Revolution Counterに商を, Result Dialに剰余を得る.

さて, 手回し計算機での開平は, 20x+1, 20x+3, ...,20x+17と引く代りに, 被開平数を最初に5倍し, 100x+05, 100x+15, ..., 100x+85と引く. Setting Dialの最下位を5に固定し, 十の桁を0,1,2,...と変えながら引く. 引ける回数は同じなので, 平方根も5倍せずに得たのと同じである. もちろん剰余は5倍になっている.

その様子を下に示す. まず200000000の5倍をResult Dialに置き, Carriageを右方へ寄せておく. 短い横線は減算を, 長い左向き矢印は, Carriageを1桁左へ移動することを示す.




赤字は十の桁が, 0,1,2,...と変る様子を, 青字はRevolution Counterが増えていく
様子を示す. 最後の剰余は, 前回の開平で得られた3836の5倍である.

2009年1月20日火曜日

開平法

1月13日から15日, プログラミング・シンポジウムに参加してきた.

手回し計算機の話題で, 開平が出来るといったら, 怪訝な顔をする人がいたので, 大きなお世話かとも思うが, 私流に説明したい.

まず筆算の方法のおさらいから. 十進法で200000000の平方根を計算してみる.

開平は基本的には除算と似ている. 除算では被除数を最初の部分剰余とし, 部分剰余から除数の倍数を引いて次の部分剰余を作るというステップを繰り返す. 最後の部分剰余が剰余になる. 各ステップで商が1桁ずつ得られる.

除数の何倍を引けば次の部分剰余が除数より小さくなるかを決めるのが, 除数の難しい点である.

開平も被開平数(radicand)を部分剰余とし, 次々と部分剰余と平方根の1桁を求めながら進行するのは除算と同じである. しかし除数の倍数として商が得られるのでなく, 平方根が除数のような相手なしに徐々に決っていくところが除算と違う.

下の図が筆算の経過で, 左部分と中部分と「=」より右の右部分からなり, 平方根が10000, 14000, 14100, 14140, 14142と順に得られる様子を示す. 右部分は中部分の値の説明で, 筆算ではいらない. この図で, aの行の中部分の200000000が被開平数で, 最初の部分剰余である. 十進の開平には平方根の1桁は, 小数点を中心にした2桁ずつの部分剰余から決める. 最初に検討するのは, 小数点から2桁ずつ左に区切っていった最後の2桁(2だけの)部分である. 2を超えない最大の平方根は1なので, それが左のaとbにある1と1になる. その1と1を掛けた1を中部分の2から引く. cの中部分の10000000は右にあるように, 被開平数から最初の平方根を引いたものである.



最初の平方根1をxとする. 次の桁の平方根をyとすると, そこまでの平方根は10x+y. 部分剰余は被開平数から(10x+y)2=100x2+20xy+y2を引いたものになる. しかしすでに100x2は引いてあるので, 20xy+y2=(20x+y)*yを引くことになる.

cとdの行の左部分の24と4がこの20x+yyに相当する. cの行の2はaとの行の1と1(つまりxx)を足したものだ. (20x+y)*yで100を超えない最大のyを探すと4なので, cとdの左に24と4を書き, 中にその積96を書き,100から引いて次の部分剰余400が得られる.

これを繰り返すとkの行で最後の部分剰余3836が得られ, 平方根が14142となる.

以前このブログに書いた個人用電卓 Happy Hacking Calculatorの平方根は剰余も得られるが, この部分剰余がスタックの2段目に得られる.

ところで, 除算でもこの剰余と除数に対し商に何を立てるか決めるのは面倒である. 一方, 手回し計算機では, 除数を引けなくなるまで繰り返し引くことである桁の商がきまる.

手回し計算機での開平法は, 下の図がその説明である. 上の図で24掛ける4を決めた代りにyを1から順に増やすのである. それまでに得た平方根をxとし, まずy=1として(20x+1)*1を引く. 次にy=2として(20x+2)*2を引くのだが,(20x+1)*1はすでに引いてあるので, (20x+2)*2-(20x+1)*1=40x+4-(20x+1)=20x+3を引く. 更にy=3とすると20x+5を引くことになる.



かくして手回し計算機でも, 無事に開平が出来るのである.