Loop is killing proccesor.

I am running the code below where I am trying to create a matrix for all the products of x digit numbers. Works fine for 1 and 2 digit numbers but three kills it. I have taken the semi colon off of 'z' and also 'x' in the first if statement so I can watch the output. For the first hundred loops (999 to 900) it is fast then gets progressively slower. The same number of tasks are being done each loop, so where my problem must be in loading the answers onto the end of my matrix 'NumLine'. Is this my problem?

function  palout =paladin(numDig)  
%NumLine = ((10^(numDig-1)^2):((10^numDig)-1)^2);

xMax = 10^numDig-1;                            %Upper bound
x = xMax;
y = x;
z = 10^(numDig-1)                          %Lowwer bound

NumLine = [];

while x >= z      
    NumLine(end+1) = x*y;      
    if y == z
        x = x-1
        y = xMax;
    else
        y = y-1;
    end    
end  
palout = NumLine;

Answer 1

[bym]

yes, you need to pre-allocate NumLine

[Scragmore]

Thanks, just clarified by asking the oracle google. I belive I understand. I declared the variable/matrix but did not allocate memory for this to be stored. So as it gets exponentially bigger it has to re allocate memory and move the matrix into it. thus the huge performance hit.

Before I close this thread could you briefly explain the consideration for the size I pre-allocate. Should it be the size of the matrix I am expecting to build or in large enough blocks it step-wise increases (does it do this) sufficiently not to hit performance too much.

Regarding pre-allocation size I briefly noticed comments on an old programming theme about the the gluttony of size of modern PC's and the over reliance on allocating large memory blocks, though I am not expecting an answer on this point. How should I consider this issue in my case.

Regards,

AD

Answer 2

[bym]

I was going to comment but I thought my reply might be better an answer. You can preallocate as long as you know apriori what the size you are expecting. If you don't know the size, the allocate in 'reasonable' chunks.

I take it from your code, you are trying to solve Project Euler #4 which ask for the largest palindrome for a product of two 3 digit numbers. So without preallocation generate the first chunk of data by using

a = (999:-1:900)'*(999:-1:900);

which gives you the first 10,000 products of two 3 digit numbers. You can search through these for the largest palindrome.

If you want to continue using loops, just allocate numbers in (100 x 100) blocks till you achieve your result. I think you will find you do not have to go beyond the range I have shown above

[Scragmore]

Thanks for the clarification and good catch on Q? No.4. Following your previous answer I had already decided to drop this approach not only because of the huge data set I was likely to produce but also the redundancy within the set. My follow up q? was more for personnel clarification on what I was doing wrong and not to do in the future rather than implementation.

I have concluded that brute force is about the only approach, so am looking for the most efficient and quickest way to do it with the tool I have (matlab). To quote 'when you have 124kBit encryption, use a spanner'.

Thanks again.

AD