[Haskell-cafe] Solving a geometry problem with Haskell
Hugh Perkins
hughperkins at gmail.com
Sat Jan 12 16:39:07 EST 2008
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?
More information about the Haskell-Cafe
mailing list