Re: [Haskell-cafe] Solving a geometry problem with Haskell

12 Jan 2008

      You can do better than this, too, actually.  It looks like you're
using isPerfectSquare inside a filter, which is given a monotone
sequence.  That means we can do:

  -- finds the intersection of two monotone sequences
  intersectMonotone :: (Ord a) => [a] -> [a] -> [a]
  intersectMonotone (x:xs) (y:ys) =
      case x `compare` y of
          EQ -> x : intersectMonotone x y
          LT -> intersectMonotone xs (y:ys)
          GT -> intersectMonotone (x:xs) ys
  intersectMonotone _ _ = []

Then you can change (filter isPerfectSquare) to (intersectMonotone
perfectSquares) and you should get a big speed boost.

Luke

On Jan 12, 2008 9:48 PM, Luke Palmer  wrote:
...
On Jan 12, 2008 9:19 PM, Rafael Almeida  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