[Haskell-cafe] Solving a geometry problem with Haskell

[Luke Palmer]

On Jan 12, 2008 9:19 PM, Rafael Almeida <almeidaraf at gmail.com> wrote:
> After some profiling I found out that about 94% of the execution time is
> spent in the ``isPerfectSquare'' function.

That function is quite inefficient for large numbers.  You might try
something like this:

isPerfectSquare n = searchSquare 0 n
    where
    searchSquare lo hi
      | lo == hi = False
      | otherwise =
          let mid = (lo + hi) `div` 2 in
          case mid^2 `compare` n of
              EQ -> True
              LT -> searchSquare mid hi
              GT -> searchSquare lo mid

Luke