kb84tkhrのブログ

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

Reasoned Schemer (99) わり算 続き

さてそうやってガードを入れた/oもこういう式では値を返さない
確かにこれを途中で止めるのは難しそう

> (run 3 (y z) (/o `(1 0 . ,y) '(0 1) z '()))
user break

しっくりこないところもあるけどだいたいストーリーは見えてきた

しっくり来てないのは「qが1より大きいときにmnより小さいことを保証する」ってあたり
これはもしかすると英語の読み方が変なんだろうと思うことにした

  • 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)

一方、nhighmで割ったら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 - nlow2^pで割り切れて答えがrhighになる
これが割り切れるための必要条件ってことだよな
十分条件でもあるのかはよくわからない