[Haskell-cafe] Looking for suggestions to improve my algorithm
Daniel Fischer
daniel.is.fischer at web.de
Wed Aug 29 19:11:52 EDT 2007
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
More information about the Haskell-Cafe
mailing list