[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
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.
More information about the Haskell-Cafe
mailing list