# [Haskell-cafe] I need help getting started

mitchell at kaplan2.com mitchell at kaplan2.com
Sun Apr 25 11:48:30 EDT 2010

Hi Daniel,

I haven't yet absorbed everything you've written.  One thing though, I
didn't know how long division takes, but yeah, obviously gcd would take
longer.

Also when I put in the correction based on Luke's note, I found out about
the perfect square problem.

With regard to style, thanks for the suggestions, I'll have to spend a
little more time going over that.

This was my first posting to this list, and you and your colleagues have
given me a real boost.

Thanks so much,

Mitchell

-----Original Message-----
From: daniel.is.fischer at web.de [mailto:daniel.is.fischer at web.de]
Sent: Sunday, April 25, 2010 4:47 AM
Cc: mitchell at kaplan2.com
Subject: Re: [Haskell-cafe] I need help getting started

Am Sonntag 25 April 2010 06:34:32 schrieb mitchell at kaplan2.com:

Luke already explained the type error, so I'll focus on the implementation.

> Hi,
>
>
>
> I'm just starting to learn, or trying to learn Haskell.  I want to write
> a function to tell me if a number's prime.  This is what I've got:
>
>
>
> f x n y = if n>=y

Since you call it with y = floor (sqrt (fromIntegral x)),
the test ought to be "n > y" or you'll classify squares of primes as
primes.

PrimeTest> primeQ 25
True

Oops.

>           then True
>           else
>           if gcd x n == 1

This is doing a lot of unnecessary work.
If gcd x n > 1, then one of the prime divisors of n must also divide x.
If n is composite, this test is never reached, otherwise (n is prime) n
divides x, so you need only test whether n divides x,

if x `rem` n /= 0

This test needs only one division, whereas calculating the gcd needs
O(log n) divisions on average. For larger primes, that's a big difference:

Prelude PrimeTest> primeF 1000000000039
True
(0.27 secs, 85607928 bytes)
Prelude PrimeTest> primeQ 1000000000039
True
(1.38 secs, 457966212 bytes)

>           then f x (n+1) y
>           else False
>

A stylistic remark,

if condition then True else somethingMore

is often better expressed as

condition || somethingMore

or using guards, so you could write f as

f x n y = (n > y) || (x `rem` n /= 0 && f x (n+1) y)

or

f x n y
| n > y          = True
| x `rem` n == 0 = False
| otherwise      = f x (n+1) y

>
>
>
>
> primeQ x = f x 2 y
>   where y = floor(sqrt(x))
>
>
>
> The compiler is very unhappy.  Apparently there's some ambiguity in
> this, and I'm kind of running around in circles.  I'd appreciate any
> help that will get me started.