[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
To: haskell-cafe at haskell.org
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.
More information about the Haskell-Cafe
mailing list