Why my program runs out of memory?
I'm trying to solve this problem: http://projecteuler.net/index.php?section=problems&id=44, and my program runs out of memory. I was wondering where I have a space leak, I thought that this program doesn't accumulate any data structures (i.e. should use constant memory): CODE BEGINS -- returns list of pairs (i, j) of indices, for which differences (gen j - gen i) -- increase, provided that gen has the following property: -- gen (i+1) - gen i > gen i - gen (i - 1) incDiffPairs gen = iterate next (0, 1) where next (i, j) = if (i == 0) || gen (j+1) - gen j < gen j - gen (i - 1) then (j, j + 1) else (i - 1, j) -- returns ith pentagonal number pentagonal i = let n = i + 1 in n * (3 * n - 1) `div` 2 -- tests if a number is pentagonal isPentagonal x = let d = 24 * x + 1 in isSquare d && (1 + sqrti d) `mod` 6 == 0 result44 = head [(pentagonal j - pentagonal i, (i, j)) | (i, j) <- incDiffPairs pentagonal, isPentagonal (pentagonal j - pentagonal i), isPentagonal (pentagonal j + pentagonal i)] CODE ENDS
On Friday 25 June 2010 20:51:44, Vladimir Ch. wrote:
I'm trying to solve this problem: http://projecteuler.net/index.php?section=problems&id=44, and my program runs out of memory.
Compile with optimisations. With -O2, after adding fairly naive isSquare and sqrti functions, it seems to run in constant memory (but very slowly, you need a better algorithm, really 8-) )
I was wondering where I have a space leak,
Profiling would tell you where the memory goes.
I thought that this program doesn't accumulate any data structures (i.e. should use constant memory):
CODE BEGINS
-- returns list of pairs (i, j) of indices, for which differences (gen j - gen i) -- increase, provided that gen has the following property: -- gen (i+1) - gen i > gen i - gen (i - 1) incDiffPairs gen = iterate next (0, 1) where next (i, j) = if (i == 0) || gen (j+1) - gen j < gen j - gen (i - 1) then (j, j + 1) else (i - 1, j)
-- returns ith pentagonal number pentagonal i = let n = i + 1 in n * (3 * n - 1) `div` 2
-- tests if a number is pentagonal isPentagonal x = let d = 24 * x + 1 in isSquare d && (1 + sqrti d) `mod` 6 == 0
result44 = head [(pentagonal j - pentagonal i, (i, j)) | (i, j) <- incDiffPairs pentagonal, isPentagonal (pentagonal j - pentagonal i), isPentagonal (pentagonal j + pentagonal i)]
CODE ENDS
On Friday 25 June 2010 20:51:44, Vladimir Ch. wrote:
I'm trying to solve this problem: http://projecteuler.net/index.php?section=problems&id=44, and my program runs out of memory. I was wondering where I have a space leak, I thought that this program doesn't accumulate any data structures (i.e. should use constant memory):
CODE BEGINS
-- returns list of pairs (i, j) of indices, for which differences (gen j - gen i) -- increase, provided that gen has the following property: -- gen (i+1) - gen i > gen i - gen (i - 1)
Oh, and: this list is not complete, e.g. (0, j) doesn't appear in the list for j > 1, so the algorithm isn't correct.
incDiffPairs gen = iterate next (0, 1) where next (i, j) = if (i == 0) || gen (j+1) - gen j < gen j - gen (i - 1) then (j, j + 1) else (i - 1, j)
-- returns ith pentagonal number pentagonal i = let n = i + 1 in n * (3 * n - 1) `div` 2
-- tests if a number is pentagonal isPentagonal x = let d = 24 * x + 1 in isSquare d && (1 + sqrti d) `mod` 6 == 0
result44 = head [(pentagonal j - pentagonal i, (i, j)) | (i, j) <- incDiffPairs pentagonal, isPentagonal (pentagonal j - pentagonal i), isPentagonal (pentagonal j + pentagonal i)]
CODE ENDS
participants (2)
-
Daniel Fischer -
Vladimir Ch.