[Haskell-cafe] Solving a geometry problem with Haskell

[Daniel Fischer]

Am Samstag, 12. Januar 2008 22:48 schrieb Luke Palmer:
> On Jan 12, 2008 9:19 PM, Rafael Almeida <almeidaraf at gmail.com> 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 = searchSquare 0 n
>     where
>     searchSquare lo hi
>
>       | lo == hi = False
>       | otherwise =
>
>           let mid = (lo + hi) `div` 2 in
>           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