# 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 Jan 28 '13 at 18:43
MichaelT, I actually never noticed that. Thanks. – Overv Jan 28 '13 at 22:26

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:
Your problem is your algorithm, not the language.

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 – Giorgio Jan 28 '13 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. Jan 28 '13 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. – Andres F. Jan 28 '13 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 – K.Steff Jan 28 '13 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.

-