Reasoned Schemer (104) logo 続き3
b
の意味がどうもつかめてないんだよな
わかった
bはやっぱりbaseなんだ
exp2o
は2の累乗(とその仲間たち)を求めるんだけどそれはb
が()
のときで
b
が(1)
なら4の累乗、b
が(1 1)
なら8の累乗、b
が(1 1 1)
なら16の累乗って
考えたらいいんだ
つまり(2の(b
の長さ+1)乗)の累乗ってわけだな
(exp2o n b q)
が(exp2o n b2 q1)
で再帰するのは
p
をb
の長さとして
n
つまり(2^(p + 1))^q
を計算する代わりに
(2^((2p + 1) + 1))^(q/2)
つまり(2^(2*(p + 1)))^(q/2)
を計算してもいいよってことだ
p + 1
をp
、q
を2q
と置きなおすとn = (2^p)^2q = (2^(2p))^q
ってこと
やっとすっきりした
というわけでexp2o
最後の行
((fresh (q1 nhigh b2 s)
(== `(1 . ,q1) q) (poso q1)
(poso nhigh)
(splito n b s nhigh)
(appendo b `(1 . ,b) b2)
(exp2o nhigh b2 q1)))))
いちばん複雑だけど、感じもつかめたしいけるんじゃないの
q
は奇数
いちばん大きな違いは(splito n b s nhigh)
か
これはどういう意味になんのかな
(appendo b ``(1 . ,b) b2) (exp2o nhigh b2 q1)
とセットで考える
えーとnhigh
はn
を2^(p + 1)
で割った答えってことだな
n=nhigh*2^(p + 1)
って書いた方が使いやすいかな?
(appendo b ``(1 . ,b) b2) (exp2o nhigh b2 q1)
は
nhigh=(2^(2*(p + 1)))^(q/2 - 1)
ってことだから
n = nhigh*2^(p + 1)
= (2^(2*(p + 1)))^(q/2 - 1)*2^(p + 1)
p + 1
をp
、q
を2q+1
と置きなおすと
n = (2^p)^(2q + 1) = (2^(2p))^q*2^p
って計算できるよ、と
こんな感じじゃないでしょうか