[Haskell-cafe] puzzle: prove this floorSqrt correct
buran at xs4all.nl
Thu Aug 12 14:51:05 EDT 2004
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.
And on glasgow-haskell-users there is a thread about (a.o.) that
subject right now :)
Nobody can be exactly like me. Even I have trouble doing it.
More information about the Haskell-Cafe