Rafael Almeida almeidaraf at gmail.com
Sat Jan 12 16:19:43 EST 2008

```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