Am Mittwoch, 29. August 2007 23:12 schrieb David Frey:
Hello Haskellers,
I have been trying to learn a bit about Haskell by solving Project Euler problems.
Good :)
For those of you who don't know what Project Euler is, see http://projecteuler.net
After solving problem 21, which is related to amicable pairs, I decided to attempt problem 95 since it is an extension of the same topic.
The full description of problem 95 is here: http://projecteuler.net/index.php?section=problems&id=95
This is the summary: "Find the smallest member of the longest amicable chain with no element exceeding one million."
I have attempted to solve this problem, but my solution is too resource hungry to search the full set of 1000000 numbers.
I haven't looked closely, but what stands out is the obscenely slow divisors function. This could be sped up if you factored the numbers using the list of primes less than 1000. But since you need the factorization of all numbers <= 1000000 (that ought to be included, the wording is 'not exceeding' - but it doesn't appear in the chain, so you won't get a false answer by omitting it), you can do even better. My suggestion: 1. create an array or a map containing the sum of divisors of each number from 1 to 1000000 1.1. 'smallest prime factor' is useful for that 2. look for chains in that array/map
I am hoping someone reading this list can suggest : - How I can improve my algorithm - An alternative algorithm that will be more efficient - Ways to profile a Haskell program to help me understand why my implementation is performing poorly.
compile with -prof -auto-all and run with euler95 +RTS -P then read euler95.prof and take a look at the ghc users guide for more profiling options
In addition to the question above, I would also be interested in comments on the style of the code. If there is a more idiomatic way to write portions of the code, I would like to see what it is.
I'll take a look and see. But don't hold your breath, 'idiomatic' isn't one of my strengths.
My solution is at the bottom of this e-mail. The program will probably run obscenely slow or die from stack overflow unless you replace [1..999999] with [1..somethingSmaller] in main.
Thanks, David Frey
Cheers, Daniel