Using `GHC 7.0.3`

, `gcc 4.4.6`

, `Linux 2.6.29`

on an x86_64 Core2 Duo (2.5GHz) machine, compiling using `ghc -O2 -fllvm -fforce-recomp`

for Haskell and `gcc -O3 -lm`

for C.

- Your C routine runs in 8.4 seconds (faster than your run probably because of
`-O3`

) - The Haskell solution runs in 36 seconds (due to the
`-O2`

flag) - Your
`factorCount'`

code isn't explicitly typed and defaulting to`Integer`

(thanks to Daniel for correcting my misdiagnosis here!). Giving an explicit type signature (which is standard practice anyway) using`Int`

and the time changes to**11.1 seconds** - in
`factorCount'`

you have needlessly called`fromIntegral`

. A fix results in no change though (the compiler is smart, lucky for you). - You used
`mod`

where`rem`

is faster and sufficient. This changes the time to**8.5 seconds**. -
`factorCount'`

is constantly applying two extra arguments that never change (`number`

,`sqrt`

). A worker/wrapper transformation gives us:

```
$ time ./so
842161320
real 0m7.954s
user 0m7.944s
sys 0m0.004s
```

That's right, **7.95 seconds**. Consistently **half a second faster than the C solution**. Without the `-fllvm`

flag I'm still getting `8.182 seconds`

, so the NCG backend is doing well in this case too.

Conclusion: Haskell is awesome.

**Resulting Code**

```
factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
where square = sqrt $ fromIntegral number
isquare = floor square
factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
where
go candidate count
| candidate > sqrt = count
| number `rem` candidate == 0 = go (candidate + 1) (count + 2)
| otherwise = go (candidate + 1) count
nextTriangle index triangle
| factorCount triangle > 1000 = triangle
| otherwise = nextTriangle (index + 1) (triangle + index + 1)
main = print $ nextTriangle 1 1
```

EDIT: So now that we've explored that, lets address the questions

Question 1: Do erlang, python and haskell lose speed due to using arbitrary length integers or don't they as long as the values are less than MAXINT?

In Haskell, using `Integer`

is slower than `Int`

but how much slower depends on the computations performed. Luckily (for 64 bit machines) `Int`

is sufficient. For portability sake you should probably rewrite my code to use `Int64`

or `Word64`

(C isn't the only language with a `long`

).

Question 2: Why is haskell so slow? Is there a compiler flag that turns off the brakes or is it my implementation? (The latter is quite probable as haskell is a book with seven seals to me.)

Question 3: Can you offer me some hints how to optimize these implementations without changing the way I determine the factors? Optimization in any way: nicer, faster, more "native" to the language.

That was what I answered above. The answer was

- 0) Use optimization via
`-O2`

- 1) Use fast (notably: unbox-able) types when possible
- 2)
`rem`

not`mod`

(a frequently forgotten optimization) and - 3) worker/wrapper transformation (perhaps the most common optimization).

Question 4: Do my functional implementations permit LCO and hence avoid adding unnecessary frames onto the call stack?

Yes, that wasn't the issue. Good work and glad you considered this.