# How to improve efficiency with functional programming?

I've recently been going through the Learn You a Haskell for Great Good guide and as practice I wanted to solve Project Euler Problem 5 with it, which specifies:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I decided to first write a function determining whether a given number is divisible by these numbers:

``````divisable x = all (\y -> x `mod` y == 0)[1..20]
``````

Then I calculated the smallest one using `head`:

``````sm = head [x | x <- [1..], divisable x]
``````

And finally wrote the line to display the result:

``````main = putStrLn \$ show \$ sm
``````

Unfortunately this took about 30 seconds to finish. Doing the same thing with the numbers 1 to 10 yields a result almost immediately, but then again the result is much smaller than the solution for 1 to 20.

I solved it earlier in C and there the result for 1 to 20 was also calculated almost instantly. This leads me to believe I'm misunderstanding how to interpret this problem for Haskell. I looked through other people's solutions and found this:

``````main = putStrLn \$ show \$ foldl1 lcm [1..20]
``````

Fair enough, this uses a built-in function, but why is the end result so much slower when doing it yourself? The tutorials out there tell you how to use Haskell, but I don't see much help with transforming algorithms into fast code.

• I should point out that many of the solved Euler problems have pdfs next to them that goes into addressing the math problem. You might try reading that pdf and implement the algorithm described in each language and then profile that.
– user40980
Commented Jan 28, 2013 at 18:43

First you need to make sure you have an optimized binary, before thinking the language is the problem. Read the Profiling and optimization chapter in Real Wolrd Haskell. It is worth noting that in most cases the high-level nature of the language costs you at least some of the performance.

However, note that the other solution is not faster because it uses a built-in function, but simply because it utilizes a much faster algorithm: to find the least common multiple of a set of numbers you need to only find a few GCDs. Compare this with your solution, which cycles through all of the numbers from 1 to `foldl lcm [1..20]`. If you try with 30, the difference between the runtimes will be even greater.

Take a look at complexities: your algorithm has `O(ans*N)` runtime, where `ans` is the answer and `N` is the number up to which you are checking for divisibility (20 in your case).
The other algorithm executes `N` times `lcm`, however `lcm(a,b) = a*b/gcd(a,b)`, and GCD has complexity `O(log(max(a,b)))`. Therefore the second algorithm has complexity `O(N*log(ans))`. You can judge for yourself which is faster.

So, to summarize:

Note that there are specialized languages that are both functional and focused on math-heavy programs, like Mathematica, which for math-focused problems is probably faster than almost anything else. It has a very optimized library of functions, and it supports the functional paradigm (admittedly it also supports imperative programming).

• I recently had a performance problem with a Haskell program and then I realized I had compiled with optimizations switched off. Switching optimization on boosted performance by about 10 times. So the same program written in C was still faster, but Haskell was not much slower (about 2, 3 times slower, which I think is a good performance, also considering I had not tried to improve the Haskell code any further). Bottom line: profiling and optimization is a good suggestion. +1 Commented Jan 28, 2013 at 14:27
• honestly think you could remove the first two paragraphs, they dont really answer the question and are probably inaccurate (they certainly play fast and loose with terminology, languages cant have a speed)
– jk.
Commented Jan 28, 2013 at 14:39
• You are giving a contradictory answer. On the one hand, you assert the OP "hasn't misunderstood anything", and that the slowness is inherent in Haskell. On the other hand, you show the choice of algorithm does matter! Your answer would be far better if it skipped the first two paragraphs, which are somewhat contradictory with the rest of the answer. Commented Jan 28, 2013 at 17:21
• Taking feedback from Andres F. and jk. I have decided to reduce the first two paragraphs to a few sentences. Thanks for the comments Commented Jan 28, 2013 at 19:07

My first thought was that only numbers divisible by all primes <= 20 will be divisible by all numbers less than 20. So you only need to consider numbers that are multiples of 2*3*5*7*11*13*17*19. Such a solution checks 1/9,699,690 as many numbers as the brute-force approach. But your fast-Haskell solution does better than that.

If I understand the "fast Haskell" solution, it uses foldl1 to apply the lcm (least common multiple) function to the list of numbers from 1 to 20. So it would apply lcm 1 2, yielding 2. Then lcm 2 3 yielding 6. Then lcm 6 4 yielding 12, and so on. In this way, the lcm function is only called 19 times to yield your answer. In Big O notation, that's O(n-1) operations to arrive at a solution.

Your slow-Haskell solution goes through the numbers 1-20 for every number from 1 to your solution. If we call solution s, then the slow-Haskell solution performs O(s * n) operations. We already know that s is over 9 million, so that probably explains the slowness. Even if all shortcuts and gets an average of half-way through the list of numbers 1-20, that's still only O(s * n/2).

Calling `head` does not save you from doing these calculations, they have to be done in order to calculate the first solution.

Thanks, this was an interesting question. It really stretched my Haskell knowledge. I wouldn't be able to answer it at all if I hadn't studied algorithms last fall.

• Actually the approach you were getting at with 2*3*5*7*11*13*17*19 probably is at least as fast as the lcm based solution. What you specifically need is 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19. Because 2^4 is the biggest power of 2 less than or equal to 20, and 3^2 is the biggest power of 3 less than or equal to 20, and so on. Commented Sep 17, 2016 at 20:57
• @semicolon While definitely faster than the other alternatives discussed, this approach also requires a pre-calculated list of primes, smaller than the input parameter. If we factor that in the runtime (and, more importantly, in the memory footprint), this approach unfortunately becomes less appealing Commented Oct 6, 2016 at 12:02
• @K.Steff Are you kidding me... you have to computer the primes up until 19... that takes a tiny fraction of a second. Your statement makes absolutely ZERO sense, the total runtime of my approach is incredibly tiny even with prime generation. I enabled profiling and my approach (in Haskell) got `total time = 0.00 secs (0 ticks @ 1000 us, 1 processor)` and `total alloc = 51,504 bytes`. The runtime is a negligible enough proportion of a second to not even register on the profiler. Commented Oct 9, 2016 at 3:37
• @semicolon I should have qualified my comment, sorry about it. My statement was related to the hidden price of calculating all primes up to N - the naïve Eratosthenes is O(N*log(N)*log(log(N))) operations and O(N) memory which means this is the first component of the algorithm that will run out of memory or time if N is really big. It doesn't get much better with the sieve of Atkin, so I concluded the algorithm will be less appealing than the `foldl lcm [1..N]`, which needs a constant number of bigints. Commented Oct 9, 2016 at 21:28
• @K.Steff Well I just tested both algorithms. For my prime based algorithm the profiler gave me (for n = 100,000): `total time = 0.04 secs` and `total alloc = 108,327,328 bytes`. For the other lcm based algorithm the profiler gave me: `total time = 0.67 secs` and `total alloc = 1,975,550,160 bytes`. For n = 1,000,000 I got for prime based: `total time = 1.21 secs` and `total alloc = 8,846,768,456 bytes`, and for lcm based: `total time = 61.12 secs` and `total alloc = 200,846,380,808 bytes`. So in other words, you are wrong, prime based is much better. Commented Oct 9, 2016 at 23:00

I wasn't initially planning on writing an answer. But I was told to after another user made the strange claim that simply multiplying the first couple primes was more computationally expensive then repeatedly applying `lcm`. So here are the two algorithms, and some benchmarks:

My algorithm:

Prime generation algorithm, giving me an infinite list of primes.

``````isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n
| isPrime n = n
| otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes
``````

Now using that prime list to calculate the result for some `N`:

``````solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 \$ takeWhile (<= n) (fromIntegral <\$> primes)
``````

Now the other lcm based algorithm, which admittedly is fairly concise, mostly because I implemented prime generation from scratch (and did not use the super concise list comprehension algorithm due to its poor performance) whereas `lcm` was simply imported from the `Prelude`.

``````solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`
``````

Now for the benchmarks, the code I used for each was simple: (`-prof -fprof-auto -O2` then `+RTS -p`)

``````main :: IO ()
main = print \$ solvePrime n
-- OR
main = print \$ solveLcm n
``````

For `n = 100,000`, `solvePrime`:

``````total time = 0.04 secs
total alloc = 108,327,328 bytes
``````

vs `solveLcm`:

``````total time = 0.12 secs
total alloc = 117,842,152 bytes
``````

For `n = 1,000,000`, `solvePrime`:

``````total time = 1.21 secs
total alloc = 8,846,768,456 bytes
``````

vs `solveLcm`:

``````total time = 9.10 secs
total alloc = 8,963,508,416 bytes
``````

For `n = 3,000,000`, `solvePrime`:

``````total time = 8.99 secs
total alloc = 74,790,070,088 bytes
``````

vs `solveLcm`:

``````total time = 86.42 secs
total alloc = 75,145,302,416 bytes
``````

I think the results speak for themselves.

The profiler indicates the the prime generation takes up a smaller and smaller percentage of the run time as `n` increases. So it is not the bottleneck, so we can ignore it for now.

This means we are really comparing calling `lcm` where one argument goes from 1 to `n`, and the other goes geometrically from 1 to `ans`. To calling `*` with the same situation and the added benefit of getting to skip every non-prime number (asymptotically for free, due to the more expensive nature of `*`).

And it is well known that `*` is faster than `lcm`, as `lcm` requires repeated applications of `mod`, and `mod` is asymptotically slower (`O(n^2)` vs `~O(n^1.5)`).

So the above results and the brief algorithm analysis should make it very obvious which algorithm is faster.