On Jan 12, 2008 10:19 PM, Rafael Almeida
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?