[Haskell-cafe] Solving a geometry problem with Haskell

[Rafael Almeida]

On Sat, 12 Jan 2008 23:36:43 +0100, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
>
> 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 >     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.