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

[Achim Schneider]

Achim Schneider <barsoap at web.de> wrote:

> 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).
> 
(and you can use a truncated sqrt as initial guess)


This may seem like cheating, but then I'm a game programmer...

-- 
(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.