[Haskell-cafe] puzzle: prove this floorSqrt correct

[Henning Thielemann]

On Thu, 12 Aug 2004, Remi Turk wrote:

> 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)

If I urgently need factors of an integer I check "factor*factor > n"
rather than "factor > intSqrt n". :-]