Reasoned Schemer (99) わり算 続き
さてそうやってガードを入れた/o
もこういう式では値を返さない
確かにこれを途中で止めるのは難しそう
> (run 3 (y z) (/o `(1 0 . ,y) '(0 1) z '()))
user break
しっくりこないところもあるけどだいたいストーリーは見えてきた
しっくり来てないのは「q
が1より大きいときにm
がn
より小さいことを保証する」ってあたり
これはもしかすると英語の読み方が変なんだろうと思うことにした
conde
で再帰するゴールが値を作り続けるとno valueになる- そういうゴールに届く前に失敗するようなゴールを入れる
- リストの長さの上限を使ってみたけど、それでは失敗させられないケースもある
- そこで
splito
の出番
なんだけど、まず数式の方を復習しておこう
n
÷m
=q
あまりr
から
n = m*q + r --- (1)
ここで
n = nhigh*2^p + nlow
q = qhigh*2^p + qlow
とおいて(1)に入れてやると
nhigh*2^p + nlow = m*qhigh*2^p + m*qlow + r --- (2)
一方、nhigh
をm
で割ったらqhigh
あまりrhigh
になったとする
(ここが)
nhigh = m*qhigh + rhigh
両辺に2^p
をかけて
nhigh*2^p = m*qhigh*2^p + rhigh*2^p
(2)から引いてやって変形すると
nlow = m*qlow+r - rhigh*2^p
rhigh*2^p = m*qlow + r - nlow
つまりm*qlow + r - nlow
は2^p
で割り切れて答えがrhigh
になる
これが割り切れるための必要条件ってことだよな
十分条件でもあるのかはよくわからない