[Haskell-cafe] puzzle: prove this floorSqrt correct

[Remi Turk]

On Thu, Aug 12, 2004 at 06:59:26PM +0200, Christian Sievers wrote:
> blaetterrascheln at web.de wrote:
> 
> > -- Here's the discrete version of Newton's method for finding
> > -- the square root.  Does it always work?  Any literature?
> 
> I recently used, without range check,
> 
> sqrtInt n = help n where
>             help x = let y = ((x + (n `div` x)) `div` 2)
>                      in if y<x then help y else x
I usually (each time I urgently need to calculate primes ;)) use
a simple intSqrt = floor . sqrt . fromIntegral
(which will indeed give wrong answers for big numbers)

> following p. 38f of Henri Cohen, A Course in Computational Algebraic Number
> Theory, where a proof and a suggestion for improvement (choose a better start
> value) is given.
> Your version should be correct as well.
> 
> As far as I know, ghc uses gmp, so I wonder if there is access to functions
> like mpz_sqrt or mpz_perfect_square_p.
there isn't.

And on glasgow-haskell-users there is a thread about (a.o.) that
subject right now :)

Greetings,
Remi

-- 
Nobody can be exactly like me. Even I have trouble doing it.