20

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.

  • 6
    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
25

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).

  • 3
    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
  • 3
    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
  • 1
    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
  • 2
    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
5

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. – semicolon Sep 17 '16 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 – K.Steff Oct 6 '16 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. – semicolon Oct 9 '16 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. – K.Steff Oct 9 '16 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. – semicolon Oct 9 '16 at 23:00
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.