[Haskell-cafe] puzzle: prove this floorSqrt correct
buran at xs4all.nl
Fri Aug 13 04:50:16 EDT 2004
On Fri, Aug 13, 2004 at 10:23:36AM +0200, Henning Thielemann wrote:
> On Thu, 12 Aug 2004, Remi Turk wrote:
> > On Thu, Aug 12, 2004 at 09:01:03PM +0200, Henning Thielemann wrote:
> > > If I urgently need factors of an integer I check "factor*factor > n"
> > > rather than "factor > intSqrt n". :-]
> > but you'll have to (^2) once every "iteration".
> > The following code only has to sqrt once.
> Right. Hm, but if you get a 'div' for free for every 'mod' (e.g. divMod)
> you could also check "factor > n `div` factor"
Though I consider the version below to be quite readable, and I
don't see how to check for "factor > n `div` factor" without
uglifying the implementation. (for merely a constant-time win.)
> > Oh, the joy of premature optimization. Or even premature coding ;)
> > -- Will lie when given stupid questions
> > isPrime 1 = False
> > isPrime 2 = True
> > isPrime n = not $ any (n`isDivBy`) (2:[3,5..intSqrt n])
> > where
> > n `isDivBy` d = n `rem` d == 0
> > intSqrt = floor . sqrt . fromIntegral
> If the numbers become too big, will 'fromIntegral' round down or up? If it
> rounds down, then intSqrt might lead to a too small result.
what I was originally typing...
] fromIntegral doesn't round, it'll have a type like Integer -> Double
] floor rounds down, and AFAICS that can't give wrong results as
] for all x: (intSqrt n + 1) ^ 2 > n
] Although intSqrt might be better renamed as floorSqrt.
Of course, it should really be
] for all x: (intSqrt n + 1) * 2 > n
which is plain wrong, so I guess you're just completely correct
and it should be:
ceilSqrt = ceiling . sqrt . fromIntegral
And this is all getting rather off-topic I'm afraid ;)
Nobody can be exactly like me. Even I have trouble doing it.
More information about the Haskell-Cafe