CODEWITHSUNDEEP
performancehaskell
Davide Spataro
Davide Spataro

Reputation: 7482

Haskell performance tuning

I'm quite new to Haskell, and to learn it better I started solving problems here and there and I ended up with this (project Euler 34).

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial >of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

I wrote a C and an Haskell brute force solution.

Could someone explain me the Haskell version is ~15x (~0.450 s vs ~6.5s )slower than the C implementation and how to possibly tune and speedup the Haskell solution?

unsigned int solve(){
unsigned int result = 0;
unsigned int i=10;
while(i<2540161){
    unsigned int sumOfFacts = 0;
    unsigned int number = i;
    while (number > 0) {
       unsigned int d = number % 10;
        number /= 10;
        sumOfFacts += factorial(d);
    }
    
    if (sumOfFacts == i)
        result += i;
    
    i++;
 }
 return result;
}

here the haskell solution

--BRUTE FORCE SOLUTION
solve:: Int
solve = sum (filter (\x-> sfc x 0 == x) [10..2540160])

--sum factorial of digits
sfc :: Int -> Int -> Int
sfc 0 acc = acc
sfc n acc = sfc n' (acc+fc r)
    where
        n' = div n 10
        r  = mod n 10   --n-(10*n')
        fc 0 =1
        fc 1 =1
        fc 2 =2
        fc 3 =6
        fc 4 =24
        fc 5 =120
        fc 6 =720
        fc 7 =5040
        fc 8 =40320
        fc 9 =362880

Upvotes: 2

Views: 433

Answers (1)

Andr&#225;s Kov&#225;cs
Andr&#225;s Kov&#225;cs

Reputation: 30103

First, compile with optimizations. With ghc-7.10.1 -O2 -fllvm, the Haskell version runs in 0.54 secs for me. This is already pretty good.

If we want to do even better, we should first replace div with quot and mod with rem. div and mod do some extra work, because they handle the rounding of negative numbers differently. Since we only have positive numbers here, we should switch to the faster functions.

Second, we should replace the pattern matching in fc with an array lookup. GHC uses a branching construct for Int patterns, and uses binary search when the number of cases is large enough. We can do better here with a lookup.

The new code looks like this:

import qualified Data.Vector.Unboxed as V

facs :: V.Vector Int
facs =
  V.fromList [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

--BRUTE FORCE SOLUTION
solve:: Int
solve = sum (filter (\x-> sfc x 0 == x) [10..2540160])

--sum factorial of digits
sfc :: Int -> Int -> Int
sfc 0 acc = acc
sfc n acc = sfc n' (acc + V.unsafeIndex facs r)
    where
        (n', r) = quotRem n 10

main = print solve

It runs in 0.095 seconds on my computer.

Upvotes: 12

Related Questions