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@gmail.com> wrote:
On Jan 12, 2008 9:19 PM, Rafael Almeida <almeidaraf@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