[Haskell-cafe] Solving a geometry problem with Haskell

[Rafael Almeida]

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