Is an infinite for loop infinite?

This is a rather theoretical Question: If i have a for loop i=1:Inf, will the loop run forever or stop, when the loop index exceeds realmax? The loop index still grows after reaching 2^53, so matlab seems to have some internal measures to counter precision loss in this case...

[Jonathan Vorndamme]

I'm sorry, I didn't see the warning message until now, so of course Walter down there is right, but I'm more interested in the why, than in the actual number of iterations.

Answer 1

[John D'Errico]

We can always try it. Perhaps we can learn something about how the loop works, done by a careful test. Remember that doubles are not well defined as integers when you bypass flintmax. This is important.

L1 = flintmax - 5;
L2 = flintmax + 10;

Below flintmax, indexing is easy. All is good. You do need to recognize that a loop even anywhere close to a number even as small as flintmax will indeed take literally forever. inf is WAY bigger. So a loop to flintmax, even if your computer running MATLAB processes 1e9 loops per second would

flintmax/(1e9*60*60*24*365)
ans =
      0.28562

still take on the order of a few months to terminate. So a loop to beyond realmax would take well beyond the point where your computer crumbles to dust, even if the earth was able to survive the sun turning into a red giant only a few billion years from now. I hope you have really good batteries in your laptop.

Disregarding the impossible, start with just getting past flintmax, a really small number in context.

L1 = flintmax - 5;
L2 = flintmax + 10;

Now, once you go beyond flintmax, numbers get confused with the next larger number. We can see that reflected in eps.

eps([L1,L2])
ans =
     1     2

Colon seems a little confused how to get there too.

(L1:L2) - flintmax
ans =
    -5    -4    -3    -2    -1     0     0     2     4     4     4     6     8     8     8    10

As I said, below flintmax, MATLAB counts perfectly, incrementing by 1 each time. Above flintmax however, sometime the increment is 0, sometimes the increment is 2. Worse, you can't even reliably predict when the increment would be 0 or 2.

I would expect 16 elements in that vector.

numel(L1:L2)
ans =
    16

Now, if I increase the upper limit by 1, we see that MATLAB actually creates a vector that has length 18 elements, not 17.

L2 = flintmax + 11;

L2 - flintmax
ans =
    12
    
numel(L1:L2)
ans =
    18

So what can we learn from this experiment? In a for loop,

count = 0;
for i = L1:L2
  count = count + 1;
end
count

count =
    18

So, indeed, the loop ran through 18 iterations, not 17. It was as if MATLAB generated the vector L1:L2, operating on each element of that vector. MATLAB does not actually generate the vector itself, but it does use the same internal logic that colon uses.

Let me try another test, that may be an illuminating test. (I hope.)

count = 0;
for ind = 1:realmax
  count = count + 1;
end

Warning: Too many FOR loop iterations. Stopping after 9223372036854775806 iterations. 
 
>> count
count =
   5.2576e+09

I broke out of the loop afterr a couple of seconds, so after it had managed to process 5e9 iterations. Note the warning message that was issued.

"Stopping after 9223372036854775806 iterations"

What is that number?

9223372036854775806/flintmax
ans =
        1024
        
log2(9223372036854775806)
ans =
    63
    
sym(2)^63
ans =
9223372036854775808

It looks like the real iteration limit would have been 2^63-2 iterations.

So even though I told it perform an infinite loop, MATLAB would have indeed given up in only something on the order of roughly 280 years on my computer.

The point is, MATLAB can indeed process a loop that runs beyond even flintmax. You won't have any degree of confidence how many iterations will be performed however. That is because as I showed above, for x beyond flintmax, eps(x) is larger than 1. So you cannot reliably predict how many iterations will be performed when an end point of the loop is greater than flintmax.

The one thing we should understand is the real maximum number of loop iterations seems to be 2^63-2. It looks like a 64 bit counter of some sort will be used internally, inside that for loop.

Will this change if the loop were to be run in single precision? I saw this conjecture made by Rik, that things will be different if run in single precision. Maybe not completely so.

L1 = single(1);
L2 = realmax('single')
L2 =
  single
   3.4028e+38
   
count = 0;
for ind = L1:L2 % both endpoints of the loop are singles
  count = count + 1; % just to give it something to do
end

Warning: Too many FOR loop iterations. Stopping after 9223372036854775806 iterations. 

Again, I broke out of the loop long before MATLAB gave up. But as you should see, it still tells me the same upper limit of iterations it would have allowed the loop to proceed before stopping it artificially, even though the loop was to operate on a single precision index. So the same 64 bit internal counter. Therefore I would not assume single precision loops will have a shorter limit on how many iterations they will really run.

Rik suggests the use of while may be a better choice. Is that true? Yes.

count = 0;
while true
  count = count + 1;
end

count
count =
   1.6164e+10

As you can see, I took a few seconds before breaking the loop this time (my internal clock said it was on the order of 10 seconds before I got bored), but even so, no warning message was ever issued. So indeed if you want a loop to run until far beyond when your computer (with that massive, multi-megaton lithium battery) has long since crumbled to dust, use while true.

[Jonathan Vorndamme]

Thanks for your answer (and also all other answers). I don't really want an infinite loop, I'd rather like to understand why matlab behaves like it does. I think your answer helped me with that: To me it seems that colon calculates the difference of the two given values, transforms it to int64, therefore capping it at intmax('int64') and than loops internally over an int64, calculating the loop index in it's type by adding the converted value of the internal int64 counter to the start value, which results in rounding errors. I tested this with the following command: k=59;j=0;for i=2^k:2^k+10;j=j+1;end;[j int64((2^k)+10-2^k)+1] varying k from 53 to 59.

[John D'Errico]

Really, the best solution is to compile code with a loop, then take a careful read through the generated code. But I refuse to go into the deep, dark forest of compiled code. 'Tis a dangerous place, where I have been told the bandersnatch runs free and wild.

You may be at least close to correct about how the code inside for works,

A for loop (as with colon) can use various loop end points that are not themselves integers.

'A':'F'
ans =
    'ABCDEF'
    
-pi:pi
ans =
  -3.1416  -2.1416  -1.1416 -0.14159  0.85841   1.8584   2.8584

But we can view either of those cases as an int64 increment, added to the start point, until start+increment exceeds the end point. This is consistent with a cap of something like intmax('int64'), as reported by the warning message. Why it seems to be 2^63-2 is an interesting question. I might postulate they special case the loop when start==end. Therefore, if we have an int64 increment, then the loop can proceed only for a MAXIMUM number of iterations of:

intmax('int64') - 1
ans =
  int64
   9223372036854775806

[Jonathan Vorndamme]

Looking at the -pi:pi case, the minus two makes sense: you need to be able to exceed the end value by (up to) one without the int64 counter overflowing - therefore, the end marker must correspond to start+intmax('int64')-1. Thanks for discussing that topic with me :)

Answer 2

[Walter Roberson]

No, if you use

for i=1:inf

then MATLAB will stop after 9223372036854775806 iterations. That number is 2^63 - 2

On my system, an empty for loop got through roughly 1.5 * 2^36 iterations in a minute, so the loop would last only about 153 years.

[Jonathan Vorndamme]

Why that number, 2^63-1 would make sense to me, as it is the maximum of int64. But why 2^63-2? also why not using uint64 and going to 2^64-1?

Answer 3

[Rik]

The for-loop will run for int64(inf) iterations. If you want an actual unending loop, consider using while true.

[Walter Roberson]

Not actually correct, Rik.

for K = 1 : inf; end

Now after a short period, control-C to terminate the loop. You will then receive the message

Warning: Too many FOR loop iterations. Stopping after 9223372036854775806 iterations.

I filed a bug report a few releases ago that the message should be when the loop starts rather than when it terminates.

[Rik]

Thanks for the correction. I'll probably delete this answer and post my suggestion as a comment on yours.

[Jonathan Vorndamme]

So is the number in the warning message wrong? because int64(inf) is 9223372036854775807 and not 9223372036854775806...

[Jonathan Vorndamme]

Also I totally agree regarding the timing of the message!

[John D'Errico]

The timing of the warning message is sort of deep in MATLAB.

for ind = 1:realmax
   drawnow
end

Warning: Too many FOR loop iterations. Stopping after 9223372036854775806 iterations. 

Inside the loop, I forced MATLAB to update figure windows, process callbacks, etc. When I did that, now the warning appears immediately. Essentially, the warning always gets issued immediately. However, the warning only shows up when MATLAB takes a chance to take a breath. Drawnow forced that to happen, so the warning pops out.