[Haskell-cafe] Solving a geometry problem with Haskell

[Luke Palmer]

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 <lrpalmer at gmail.com> wrote:
> 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
>