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

On Sat, 12 Jan 2008 23:36:43 +0100, Daniel Fischer wrote:

Am Samstag, 12. Januar 2008 22:48 schrieb Luke Palmer:

...

On Jan 12, 2008 9:19 PM, Rafael Almeida wrote:

...

After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function.

That function is quite inefficient for large numbers. You might try something like this:

isPerfectSquare n > where searchSquare lo hi

| lo = hi > | otherwise > let mid > case mid^2 `compare` n of EQ -> True LT -> searchSquare mid hi GT -> searchSquare lo mid

Luke

I don't want to be a spoil-sport, but that won't help much either. And although the logic of the programme is correct, the numbers involved are so large that I'd expect the running time to be rather years than days (it took a minute to solve for the smallest cathetus of 6 triangles, 128). Suppose the answer were 10^9 (it's much larger, actually). Then the limit for the other cathetus would be roughly 5*10^17 and for all these values it has to be checked whether n^2 + y^2 is a perfect square. If one check took a nanosecond, that would be roughly 5*10^8 seconds or nearly 16 years. Rafael, you have some good starts, but to get the answer in a reasonable time, you must employ some more algebra. Find a way to determine a cathetus of how many triangles a number is without actually constructing them is a good step.

Cheers, Daniel

Now you really conviced me that the algorithm isn't right. Although I already thought I needed to come up with a new algorithm when the GMP's perfect square function didn't help. I thank for all the feedback on how to make isPerfectSquare faster, though. It has been educational. I'm trying to come up with something other than constructing the triangles, but maybe I'm just not that strong at algebra. Thanks for de feedback, though.