MATLAB runs out of memory during program execution

Question

I have been happily using MATLAB to solve some project Euler problems. Yesterday, I wrote some code to solve one of these problems (14). When I write code containing long loops I always test the code by running it with short loops. If it runs fine and it does what it's supposed to do I assume this will also be the case when the length of the loop is longer.

This assumption turned out to be wrong. While executing the code below, MATLAB ran out of memory somewhere around the 75000th iteration.

c=1;
e=1000000;

for s=c:e
    n=s;
    t=1;
    while n>1
        a(s,t)=n;
        if mod(n,2) == 0
            n=n/2;
        else
            n=3*n+1;
        end
        a(s,t+1)=n;
        t=t+1;

    end
end

What can I do to prevent this from happening? Do I need to clear variables or free up memory somewhere in the process? Will saving the resulting matrix a to the hard drive help?

Answer 1

Simply put, there's not enough memory to hold the matrix a.

Why are you making a two-dimensional matrix here anyway? You're storing information that you can compute just as fast as looking it up.

There's a much better thing to memoize here.

EDIT: Looking again, you're not even using the stuff you put in that matrix! Why are you bothering to create it?

Answer 2

Short Answer:Use a 2d sparse matrix instead.

Long Answer: http://www.mathworks.com/access/helpdesk/help/techdoc/ref/sparse.html

Answer 3

Here is the solution, staying as close as possible to your code (which is very close, the main difference is that you only need a 1D matrix):

c=1;
e=1000000;
a=zeros(e,1);
for s=c:e
    n=s;
    t=1;
    while n>1
        if mod(n,2) == 0
            n=n/2;
        else
            n=3*n+1;
        end
        t=t+1;

    end
    a(s)=t;
end
[f g]=max(a);

This takes a few seconds (note the preallocation), and the result g unlocks the Euler 14 door.

Answer 4

The code appears to be storing every sequence in a different row of a matrix. The number of columns of that matrix will be equal to the length of the longest sequence currently found. This means that a sequence of two numbers will be padded with a bunch of right hand zeros.

I am sure you can see how this is incredibly inefficient. That may be the point of the exercise, or it will be for you in this implementation.

Better is to keep a variable like "Seed of longest solution found" which would store the seed for the longest solution. I would also keep a "length of longest solution found" keep the length. As you try every new seed, if it wins the title of longest, then update those variables.

This will keep only what you need in memory.