[Haskell-cafe] Looking for suggestions to improve my algorithm

[Daniel Fischer]

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