第3章 練習問題 E

• isqrt :: Float -> Integer は非負数の平方根の床を返す関数である． 3.3 節の戦略に従って，isqrt x を log x ステップで計算する実装を構成せよ．

isqrt :: Float -> Integer
isqrt x = fst (until unit (shrink x) (bound x))
  where
    unit (m,n) = m + 1 == n
   
shrink :: Float -> Interval -> Interval
shrink x (m, n) = if (p * p) leq x then (p, n) else (m, p)
  where
    p = (m + n) div 2

bound :: Float -> Interval
bound x = (0, until above (* 2) 1)
  where
    above n = x lt (n * n)