AW: [Haskell-cafe] Solving a geometry problem with Haskell

[Nicu Ionita]

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 at haskell.org 
> [mailto:haskell-cafe-bounces at haskell.org] Im Auftrag von 
> Rafael Almeida
> Gesendet: Samstag, 12. Januar 2008 22:20
> An: haskell-cafe at 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 at haskell.org 
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>