AW: [Haskell-cafe] Solving a geometry problem with Haskell
Nicu Ionita
nionita at lycos.de
Sun Jan 13 05:48:09 EST 2008
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
>
More information about the Haskell-Cafe
mailing list