[Haskell-cafe] Solving a geometry problem with Haskell
Luke Palmer
lrpalmer at gmail.com
Sat Jan 12 17:04:18 EST 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 <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
>
More information about the Haskell-Cafe
mailing list