February 14th, 2007
( Collapse )
So I decided I wanted to dork around with Haskell, just for grins. I downloaded WinHugs and started looking at a tutorial.
I got as far as the recursive definition of prime (a function to test if a number is prime or not) before my evil side manifested. You can see the code for this function in the lower-right of the screen shot. It probably isn't obvious to any non-Haskeller, but the algorithm the tutorial gave was:
"A number N is non-prime if there is another number K such that: 2 < K < N, and N is evenly divisible by K." In other words, the approach was to take your number, N, and try and integer divide it by every number from 2 to N-1 and see if any of them divided it evenly!
Now I quite understand this was only for tutorial purposes, and nobody would actually implement a prime test function this way. Still, it was screechingly obvious to me that this algorithm was no AKS primality test. Heck, it wasn't even a Sieve of Eratosthenes! I couldn't resist making the obvious optimization of only checking from 2 up to (N/2). (I know you only strictly need to check up to sqrt(N), but I don't know how to do integer square roots in Haskell yet.) Even so I was pretty sure this thing was going to be dog-slow. Unsure of exactly HOW slow it was going to be on my "mere" 850 MHz Pentium 3, and also unsure of what format Haskell uses internally for integers, I decided to start off with a few random tests.
( Collapse )