[Haskell-cafe] puzzle: prove this floorSqrt correct

blaetterrascheln at web.de blaetterrascheln at web.de
Thu Aug 12 08:49:19 EDT 2004


-- Here's the discrete version of Newton's method for finding
-- the square root.  Does it always work?  Any literature?

floorSqrt :: Integer -> Integer
floorSqrt n | n>=1 = detect (iterate (\x->(x+n`quot`x)`quot`2) 1)
  where detect (x:xs@(y:z:_)) | x==z      = min x y
                              | otherwise = detect xs

isFloorSqrt n x = x*x <= n && n < (x+1)*(x+1)
main = print$ all (\n->isFloorSqrt n (floorSqrt n)) [1..1000000]

________________________________________________________________
Verschicken Sie romantische, coole und witzige Bilder per SMS!
Jetzt neu bei WEB.DE FreeMail: http://freemail.web.de/?mc=021193



More information about the Haskell-Cafe mailing list