[Haskell-cafe] puzzle: prove this floorSqrt correct
Henning Thielemann
iakd0 at clusterf.urz.uni-halle.de
Thu Aug 12 15:01:03 EDT 2004
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". :-]
More information about the Haskell-Cafe
mailing list