[Haskell-beginners] Perfect numbers

Kurt Hutchinson kelanslists at gmail.com
Thu Oct 2 08:57:54 EDT 2008

On Thu, Oct 2, 2008 at 12:45 AM, Matthew Williams
<Matthew_Williams at xyratex.com> wrote:
> I'm using GHC to run it. My problem / question is this: It's running quite a
> lot slower than equivalent programs in erlang and python. I suspect it's
> down to the way I've written it. Any thoughts (or comments in general)

Although Ben's algorithm suggestions are wise (just test up to the
square root and add the matching divisor), even without those
improvements, I get huge speed-up just using Int instead of Integer
and compiling with -O2 instead of using ghci. On my machine, just
compiling it takes the time down from about 30 seconds to 4.5. Then
switching to Int takes it down to 1.2 seconds. I guess maybe the
Python interpreter is a bit more deft at this type of problem than the
GHC interpreter.

In case you're wondering, since you said you're new to Haskell, the
Int type uses machine storage (like 'int' in C, with the same bound
restrictions), whereas the Integer type is a bit more abstract and can
increase without limit. That's why Integer is a bit more costly to
calculate with.

Another style tip: if your list comprehension is only used to filter
out elements (like in your 'do_perfect' function), it's clearer to use
the Prelude function 'filter':

  do_perfect = filter is_perfect


More information about the Beginners mailing list