Is an infinite for loop infinite?

18 Ansichten (letzte 30 Tage)
Jonathan Vorndamme
Jonathan Vorndamme am 3 Jul. 2020
Kommentiert: John D'Errico am 3 Jul. 2020
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...
  1 Kommentar
Jonathan Vorndamme
Jonathan Vorndamme am 3 Jul. 2020
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.

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

John D'Errico
John D'Errico am 3 Jul. 2020
Bearbeitet: John D'Errico am 3 Jul. 2020
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.
  3 Kommentare
John D'Errico
John D'Errico am 3 Jul. 2020
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
Jonathan Vorndamme am 3 Jul. 2020
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 :)

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (2)

Walter Roberson
Walter Roberson am 3 Jul. 2020
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.
  1 Kommentar
Jonathan Vorndamme
Jonathan Vorndamme am 3 Jul. 2020
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?

Melden Sie sich an, um zu kommentieren.


Rik
Rik am 3 Jul. 2020
Bearbeitet: Rik am 3 Jul. 2020
The for-loop will run for int64(inf) iterations. If you want an actual unending loop, consider using while true.
  5 Kommentare
Jonathan Vorndamme
Jonathan Vorndamme am 3 Jul. 2020
Also I totally agree regarding the timing of the message!
John D'Errico
John D'Errico am 3 Jul. 2020
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.

Melden Sie sich an, um zu kommentieren.

Kategorien

Mehr zu Loops and Conditional Statements finden Sie in Help Center und File Exchange

Produkte


Version

R2017b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by