Reasoned Schemer (28) わり算 終わり
で、ふたつに分けたらわり算がどうなるというのか
わり算短くなったなーと思ったら
(defrel (/o n m q r)
(conde
((== '() q) (== r n) (<o n m))
((== '(1) q) (==lo m n) (+o r m n) (<o r m))
((poso q) (<lo m n) (<o r m) (n-wider-than-mo n m q r))))
まだ割ってなかった!
q
が正で、n
がm
よりも大きい場合、実際の計算はn-wider-than-mo
で行う
(で、r
はm
より小さくなるようにする)
まず数式で説明があります
ざっくり言うと
n=m*q+r --- (1)
を満たすn
、m
、q
、r
を求めることは、
nhigh=m*qhigh+rhigh --- (2)
m*qlow+r-nlow=rhigh*2^p --- (3)
ここで
n=nhigh*2^p+nlow
q=qhigh*2^p+qlow
r=rhigh*2^p+qlow
を満たすnhigh
、nlow
、m
、qhigh
、qlow
、rhigh
、rlow
を求めることと同じ、
ってことを言いたいようです
っていうことをコードに書き下すとn-wider-than-mo
になります
(1)は(/o n m q r)
や(n-wider-than-mo n m q r)
に対応してますね
(3)はm*qlow+r-nlow
の下位p
ビットが0ということですから、splito
を使って
(splito m*qlow+r-nlow r '() rhigh)
と書くことができます
(実際にはこういう書き方はできませんが)
n=nhigh*2^p+nlow
は、r
のビット長をp
としたときの(splito n r nlow nhigh)
に対応します
これでなにがうれしいかというと、nlow
やqlow
などの数はたかだかp
ビットの数なので
範囲が決まっているから、どんどん大きな数で無限に試さなくてもいい、ってことだそうです
処理系はその「範囲」をどうやって認識するんでしょうか
わかりません
これでやっとわり算おわりです
このわり算の練習でいいたいことはなんだったんでしょうか
まさか関係プログラミングでわり算するのはこんなに大変なんだよ、ってことじゃないでしょう
範囲を区切ることが大事だよ、ってことでしょうか
あと、「一番右まで見てダメだったら戻る」的な動きを特に意識して書く必要はないよ、ってことも
あるかもしれませんが、いろいろ複雑過ぎて目立ってませんね
ところでそもそも(2)って書けるのが前提みたいになっちゃってるところがいまひとつしっくりきてないんですよねえ
説明されてませんが説明不要なくらい当たり前なことなんでしょうか
なにかに気づいてないだけかな
(2)であれば(3)でなければならない、っていうことはこの説明でわかるんですけどね