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

[Achim Schneider]

Achim Schneider <barsoap at web.de> wrote:

> "Rafael Almeida" <almeidaraf at gmail.com> wrote:
> 
> > perfectSquares :: [Integer]
> > perfectSquares = zipWith (*) [1..] [1..]
> 
> > isPerfectSquare :: Integer -> Bool
> > isPerfectSquare x = (head $ dropWhile (<x) perfectSquares) == x
> 
> what about
> 
> module Main where
> 
> isPerfectSquare :: Integer -> Bool
> isPerfectSquare n = sqrrt == fromIntegral (truncate sqrrt)
>     where sqrrt = sqrt $ fromIntegral n
> 
> ? It's a hell alot faster, but I have no idea if some numerical
> property of square roots could make it give different results than
> your version, in rare cases.
> 
Well, even if so, I bet calculating the square root by successive
approximation using integers would still be faster, it's O(ld(n))
instead of O(n).


-- 
(c) this sig last receiving data processing entity. Inspect headers for
past copyright information. All rights reserved. Unauthorised copying,
hiring, renting, public performance and/or broadcasting of this
signature prohibited.