Hi Rafael, I have just two ideas, that could improve your strategy to reduce the computation time: 1. perhaps there is also a minimum (not only a maximul) for the values you should try 2. is the function howManyTriangles monotone? If yes, then you could try to solve: howManyTriangles n = 47547 by finding an upper n, nmax, where howManyTriangles nmax > 47547, and than using Euler to reduce the interval (from 12 to nmax, then probably from (12 + nmax)/2 to nmax, a.s.o) Then you will have ~ ln nmax computations of the function, which could be better than computing it from 1 to ... Nicu Ionita
-----Ursprüngliche Nachricht----- Von: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] Im Auftrag von Rafael Almeida Gesendet: Samstag, 12. Januar 2008 22:20 An: haskell-cafe@haskell.org Betreff: [Haskell-cafe] Solving a geometry problem with Haskell
Hello,
I have been browsing through the problems at projecteuler.net and I found one that seemed interesting. It's the problem 176, I'll state it here:
The four rectangular triangles with sides (9,12,15), (12,16,20), (5,12,13) and (12,35,37) all have one of the shorter sides (catheti) equal to 12. It can be shown that no other integer sided rectangular triangle exists with one of the catheti equal to 12.
Find the smallest integer that can be the length of a cathetus of exactly 47547 different integer sided rectangular triangles.
I thought I've solved it nicely, only to find later on that my solution was too slow (it has been running for almost three days now). While I was creating my solution I used literate haskell, which I think helped me a bunch to think about the problem. I wrote it originally in portuguese -- the portuguese literate version has all the attempts I've made until getting to the final one. For posting it here I've translated the reasoning around the attempt that solved the problem -- although it does it very slow -- into a new .lhs file:
http://www.dcc.ufmg.br/~rafaelc/problem176.lhs
After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function. So I began researching about better ways to write that functio. Someone pointed to me on #haskell that the C library gmp has such a function. So I went ahead and wrote a C version of the program using gmp:
http://www.dcc.ufmg.br/~rafaelc/problem176.c
It's not the prettiest C code, as I did it really quickly, simply translating haskell code into C, but I believe it works. That C solution has been running for more than one hour now and no solution has come up yet. So I don't think it's worthed even writing a faster isPerfectSquare in haskell.
As I was translating from Portuguese to English I revisited my logic and I can't see any problems with it. I think the problem is only of slowness, really. Does anyone have a better idea for how I should try to solve this problem? I'm all out of ideas.
[]'s Rafael _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe