2 進表現
これは,は,,,で構成できる.ということは,はとで構成できる.つまり,
となるような演算子を定義できる.そうするとは,の 2 進表現を逆順にならべたものと,
を対応させて構成できる.このときはで構成できる.これをHaskellのコードにすると以下のようになる.これで でもなんとかなりそう.
p0002 u = (a+b-1) `div` 2 where (a,b) = foldr1 f . takeWhile ((u>=).fst) $ bfib3s x `f` y | fst z > u = y | otherwise = z where z = x `oplus` y oplus :: (Integer,Integer) -> (Integer,Integer) -> (Integer,Integer) (a,b) `oplus` (c,d) = (b*c + a*d - ac, b*d + ac) where ac = a*c bfib3s :: [(Integer,Integer)] bfib3s = iterate dbl (2,3) dbl :: (Integer,Integer) -> (Integer,Integer) dbl x = x `oplus` x