[Haskell-cafe] Solving a geometry problem with Haskell
Daniel Fischer
daniel.is.fischer at web.de
Sat Jan 12 17:36:43 EST 2008
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
More information about the Haskell-Cafe
mailing list