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: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] Im Auftrag von > Rafael Almeida > Gesendet: Samstag, 12. Januar 2008 22:20 > An: [email protected] > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
