# Can you count to infinity?

On my recent question on twitter I asked how this piece of code would behave in case of built-in arithmetic types (which I inaccurately referred to as basic numeric types):

```template<typename T> T f() {
T t{};
while (t < t+1) {
t++;
}
return t;
}```

The question is more complex than it seems.

For the sake of this discussion, I’ll also consider a slightly modified version of the same code:

```template<typename T> int f() {
T t{};
while (t < t+1) {
t++;
}
return 1;
}```

I’ll call the first version v1, and the second v2.

First of all, the “obvious” case: for unsigned integral types, the standard mandates “Unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer”. Under these laws, for `unsigned int`(*) the increment of a variable `t` whose value is 2n – 1 will give `0`. The loop will terminate, and the result is `std::numeric_limits<unsigned int>::max()`. So, we can exclude the cases “Loop never terminates” and “Nobody knows” because there’s at least one case when somebody knows that the loop terminates.

What happens with `unsigned short` and `unsigned char`? Well, it’s complicated. They can be promoted to either `int` or `unsigned int`, they’re converted to the firsto one capable of containing the whole range. In practice, the conversion to `unsigned int` only happens if the size of `unsigned char` and/or `unsigned short` is exactly the same of `unsigned int`: in this case we go back to the previous case of `unsigned int`. In the other cases (which are all normal platform), our loop ends up being always infinite because our value is always smaller than its `int`-promoted-and-incremented version.

For signed integral types, I wasn’t able to pinpoint the exact wording in the standard, but it’s well known that overflow is Undefined. The options for `int`(*) are two:

1. The compiler makes no assumption, generates the code, and get caught by surprise if at a certain point `t < t+1` evaluates to `false`, terminating the loop. Our result will be again `std::numeric_limits<T>::max()`.
2. The compiler wants to be smart and assume that the condition `t < t+1` always evaluates to `true`, and thus generates an infinite loop. But infinite loops are also Undefined Behaviour as well, and in theory the compiler is allowed to assume that the loop will terminate. In this case, in v1 it won’t be able to decide at compile time a value for `t`, while in v2 it could assume a return 1. In practice, I found no compiler optimizing v2 to a simple `return 1;`, but if you can try yourself hereUPDATE (2018/02/19 14:56): Furkas noted that ICC does optimize that (see comments). Oddly, I found out that version 16, 17 and 18 optimize it correctly, but version 13 completely ignores the `+5` that he added after the return.

So, for `int`(*) the termination is really Undefined. For small ints, we fall in the same case in the degenerate case when they are equivalent (as happened in the unsigned case), or we end up with an infinite loop for proper smaller ints, those where `sizeof(T) < sizeof(int)`.(*)

But there’s more!

What about floating point? Well, in such case the result isn’t defined (termination), and isn’t undefined: it’s Implementation Defined.

First let’s consider an IEEE-754 compliant implementation (those where `std::numeric_limits<T>::is_iec559 == true`), even here we have two different possible behaviors:

If `std::numeric_limits<T>::round_style` is `round_toward_zero` or `round_toward_neg_infinity` the result is well defined: it will terminate at 224 for binary32 (on most implementation `float`) and 254 for binary64 (on most implementation `double`), and i`std::numeric_limits<T>::round_style` is `round_to_nearest` the result is probably going to be the same (it is, on the processor I was able to test). Those numbers are the first values where rounding error becomes ±1 (so, a simple increment can’t be represented and must be rounded).

If `std::numeric_limits<T>::round_style` is `round_toward_infinity`, the result is going to be `std::numeric_limits<T>::infinity()`: I wasn’t able to test it anywhere, but my assumption is that when `t` reaches `infinity`, the expression `t < t+1` becomes `infinity < infinity + 1`, which in turn becomes `infinity < infinity`, which is `false` by definition in IEEE-754.

For non-IEEE-754 floating point numbers, with `round_toward_infinity` and a different infinity rules (one where `infinity < infinity` equals `true`, maybe),  the loop will be infinite.

And now for something completely different, non-arithmetic types!

First, there’s the strange case of dr. `bool`: this is only valid until C++14, and the result is even more counterintuitive than before, because `t+1` and `t++` are actually very different beasts:

• the expression `t++` is (was, until C++14) by definition equivalent to the statement `t = true`
• the expression `t+1` is of type `int`, and is obtained by casting the `bool t` to `int`, and then adding `1`.

Possible values of this expression `t+1 == 1` when `t` is `false`, and `t+1 == 2` when `t` = `true`, thus `t < t+1` becomes a bool-to-int comparison, and is equivalent to `(int)t < t+1`, so it’s `0 < 1` when `t` is `false` and `1 < 2` when `t` is `true`, thus the condition is always `true`, and the loop is infinite.

Finally, pointers! In this last case, we’re in the open sea of UB, first of all because we start with a null pointer and try to increment it: this itself is NOT UB, because we’re not dereferencing, but we’re not pointing to an array (by definition the comparison between two pointers make sense only if they point inside the same array, or struct), so the comparison result is UB. Even if we change the code to find a sensible initialization (e.g. at the beginning of an array), it’s just a matter of time: array are finite, and at a certain point in time the variable `t` will point after the last element of the array, and from the next iteration it will start sailing toward infinity (eventually wrapping around the end of the world, and proving that the earth is round and not flat).

* UDPATE (2018/02/22 0:54): The discussion of smaller ints has been updated after vrt3’s comment.

1. Furkan

You are saying that no compiler optimized V2, but it looks to me that ICC is optimizing away the function call: https://godbolt.org/g/CUF6Dq

• Marco Foco

Oh, nice catch, thank you! Fixing…

2. vrt3

You don’t always get a result even for small unsigned integral types: t < t + 1 will always be true because of integer promotion. Example: if T is unsigned char and t is 255, t + 1 is the int 256 and not the unsigned char 0, resulting in an infinite loop.

You can fix it by rewriting the condition as t < T(t + 1).

• Marco Foco