kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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が正で、nmよりも大きい場合、実際の計算はn-wider-than-moで行う
(で、rmより小さくなるようにする)

まず数式で説明があります
ざっくり言うと

n=m*q+r --- (1)

を満たすnmqrを求めることは、

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

を満たすnhighnlowmqhighqlowrhighrlowを求めることと同じ、
ってことを言いたいようです
っていうことをコードに書き下すと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)に対応します

これでなにがうれしいかというと、nlowqlowなどの数はたかだかpビットの数なので
範囲が決まっているから、どんどん大きな数で無限に試さなくてもいい、ってことだそうです

処理系はその「範囲」をどうやって認識するんでしょうか
わかりません

これでやっとわり算おわりです
このわり算の練習でいいたいことはなんだったんでしょうか
まさか関係プログラミングでわり算するのはこんなに大変なんだよ、ってことじゃないでしょう
範囲を区切ることが大事だよ、ってことでしょうか
あと、「一番右まで見てダメだったら戻る」的な動きを特に意識して書く必要はないよ、ってことも
あるかもしれませんが、いろいろ複雑過ぎて目立ってませんね

ところでそもそも(2)って書けるのが前提みたいになっちゃってるところがいまひとつしっくりきてないんですよねえ
説明されてませんが説明不要なくらい当たり前なことなんでしょうか
なにかに気づいてないだけかな
(2)であれば(3)でなければならない、っていうことはこの説明でわかるんですけどね