[Haskell-cafe] Solving a geometry problem with Haskell

[Hugh Perkins]

On Jan 12, 2008 10: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.

I guess that Haskell's referential transparence means the answers to
the isPerfectSquare will be cached, ie automatically memoized? (not
sure if is correct term?)

Just out of interest, what is the upper bound for the catheti in the
question?  How much memory is the perfectSquares list taking up?

One thought:
- you're calculating the square by multiplying two numbers, maybe that
could be done more quickly

Quick back of envelope:

1 x 1 = 1
2 x 2 = 4   = 1 + 1 + 2
3 x 3 = 9   = 4 + 2 + 3
4 x 4 = 16  = 9 + 3 + 4

... in other words, you can use dynamic programming to calculate each
perfect square, getting each square as:

square(n+1) = square(n) + (n - 1) + (n)

Maybe this could save some CPU?