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

Achim Schneider barsoap at web.de
Sat Jan 12 18:42:24 EST 2008

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

> [perfect square problem]

most of this is shamelessly stolen from

(^!) :: 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)
*Main> isSquare (2^1024+1)
*Main> isSquare (2^1024-1)
*Main> isSquare (2^2^16)

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. 

More information about the Haskell-Cafe mailing list