Reasoned Schemer (39) 8章 未体験ゾーン2
(base-three-or-moreo n b q r)
名前からしてb
(baseだろう)が3以上の時のn = b^q + r
の関係に違いない
baseが2のときはexp2o
base-three-or-moreo
にはconde
は出てこないので
全部いっぺんに見ないといけない
いっぱい式があるけどどれが大事な式なのか
いちばん大事なのはたぶん(+o bq r n)
だろう
ここからさかのぼればいいかな
r
とn
は引数にあるやつだからbq
がどこから出てきたか
意味的にはb^q
であることは間違いないんだけど
bq
は(*o bqlow bqd bq)
で決まる
ここから各種関係もを使って遡っていくと
bq = bqlow * bqd # (*o bqlow bqd bq) から
= b^qlow * bqd # (repeated-mulo b qlow bqlow) から
= b^qlow * b^qd # (repeated-mulo b qd bqd) から
= b^qlow * b^(q - qlow) # (+o qlow qd q) から
= b^q
つじつまは合ってる
qlow
は消えてしまったけど、
b^q
をb^qlow
とb^(q - qlow)
に分けて求めたとも言えるな
割り算もそんなことしてたし
bq
の式からすると別にqlow
がいくつだって答えは同じなんだから
no valueにならないようにガードするための値なんだろう
qlow = qlow1 - 1 # (+o qlow '(1) qlow1) から
= nw // bw - 1 # (÷o nw bw qlow1 s) から
ここで
bw1
は(exp2o b '() bw1)
、nw1
は(exp2o n '() nw1)
に
2^q <= n
(ただしq
は最大)という関係、って感じ?
の仮説を採用すると
bw1
は2^bw1 <= b
を満たす最大の自然数、
nw1
は2^nw1 <= n
を満たす最大の自然数、
ってことになる
たぶんこれはここでは
b
やw
のビット表現の長さより小さい最大の自然数、と読む
(ということは=
は含んでない方が都合がいい?)
さらに
nw = nw1 + 1 # (+o nw1 '(1) nw) から
bw = bw1 + 1 # (+o bw1 '(1) bw) から
からnw
やbw
はn
やb
のビット表現の桁数、ってことだろう
w
はwidthかな?
なんで3以上の底のlogを計算するのに2の累乗が出てくるのかと思ったけど
そういうわけか
(≦lo qlow q)
や(≦o qd qdhigh)
、(<o n bq1)
あたりで
ガードしてるってことだろう