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

[Achim Schneider]

"Rafael Almeida" <almeidaraf at gmail.com> wrote:

> [perfect square problem]

most of this is shamelessly stolen from
http://www.haskell.org/haskellwiki/Generic_number_type#squareRoot

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n
 
isSquare :: Integer -> Bool
isSquare n =
   let newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep $ truncate $ sqrt $ fromIntegral n
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
       root =  head $ dropWhile (not . isRoot) iters
   in root^!2 == n

*Main> isSquare (2^1024)
True
*Main> isSquare (2^1024+1)
False
*Main> isSquare (2^1024-1)
False
*Main> isSquare (2^2^16)
True

the last one take a bit less than 20 secs on my pc. And 2^2^16 is a
number that takes at least an hour to pronounce.

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