3 ms·

I've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what

I've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what it decided is an infinite loop?

junon 5y ago
Yes.
Thiez 5y ago
The C++ standard allows compilers to assume that loops terminate. Since there is only one way to exit the loop (`return true;`) the compiler can assume that this line will eventually be reached. Since the rest of the loop has no side effects, the compiler can optimize it out. So the compiler doesn't actually need to figure out if the loop is infinite or not.
- Denvercoder9 5y ago
  > The C++ standard allows compilers to assume that loops terminate. Technically, it doesn't, but it requires programs to make forward progress, which is defined as either terminating, calling I/O functions, accessing a volatile variable or performing an atomic or synchronization operation. Infinite loops that'll eventually do one of these are perfectly valid C++ and don't have to terminate.
  - HelloNurse 5y ago
    It optimizes "waste an unpredictable time doing arithmetic without side effects, then return 1" to "return 1 without looking at the input". The relation between that machine arithmetic and the Collatz conjecture is irrelevant.
    - Denvercoder9 5y ago
      I don't think you're responding to the right comment?
WJW 5y ago
LLVM optimizes out the infinite loop, because the C++ standard defines that all programs must be able to make forward progress and so removing this loop does not alter the result of the program. Thus, collatz() as written in the tweet will always return true when optimized by LLVM. This says nothing about the conjecture being true or not, it is solely an artifact of the C++ standard being written a certain way. But also a layer deeper, collatz() takes a uint128 as input and the Collatz conjecture has already been proven to be true for all numbers that would fit into a uint128. So LLVM arrives to the correct answer (`return true`) because of the wrong reason, mathematically speaking.
- ludocode 5y ago
  This doesn't exactly follow the Collatz conjecture because multiplication by 3 will be truncated to a 128-bit unsigned int. It is possible that this truncation causes a loop. Even though the Collatz conjecture has been tested for all numbers in this range, it has probably not been tested with this overflow effect.
  - plasticchris 5y ago
    Edit: removing my comment, I misunderstood.
    - WJW 5y ago
      Not so, since the fact that it is in the range does not mean it will steadily go downwards. It might have numbers much bigger than the maximum value for a uint128 somewhere in its Collatz sequence and it is possible (though unlikely) that one of those numbers modulo the maximum value for a uint128 is the original number again. (That is, the modulo operation might introduce loops that are not present in the normal Collatz sequence because mathematical integers don't overflow)

I've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what it decided is an infinite loop?

junon 5y ago

Yes.

Thiez 5y ago

The C++ standard allows compilers to assume that loops terminate. Since there is only one way to exit the loop (`return true;`) the compiler can assume that this line will eventually be reached. Since the rest of the loop has no side effects, the compiler can optimize it out. So the compiler doesn't actually need to figure out if the loop is infinite or not.

Denvercoder9 5y ago
> The C++ standard allows compilers to assume that loops terminate. Technically, it doesn't, but it requires programs to make forward progress, which is defined as either terminating, calling I/O functions, accessing a volatile variable or performing an atomic or synchronization operation. Infinite loops that'll eventually do one of these are perfectly valid C++ and don't have to terminate.
- HelloNurse 5y ago
  It optimizes "waste an unpredictable time doing arithmetic without side effects, then return 1" to "return 1 without looking at the input". The relation between that machine arithmetic and the Collatz conjecture is irrelevant.
  - Denvercoder9 5y ago
    I don't think you're responding to the right comment?

WJW 5y ago

LLVM optimizes out the infinite loop, because the C++ standard defines that all programs must be able to make forward progress and so removing this loop does not alter the result of the program. Thus, collatz() as written in the tweet will always return true when optimized by LLVM. This says nothing about the conjecture being true or not, it is solely an artifact of the C++ standard being written a certain way. But also a layer deeper, collatz() takes a uint128 as input and the Collatz conjecture has already been proven to be true for all numbers that would fit into a uint128. So LLVM arrives to the correct answer (`return true`) because of the wrong reason, mathematically speaking.

ludocode 5y ago
This doesn't exactly follow the Collatz conjecture because multiplication by 3 will be truncated to a 128-bit unsigned int. It is possible that this truncation causes a loop. Even though the Collatz conjecture has been tested for all numbers in this range, it has probably not been tested with this overflow effect.
- plasticchris 5y ago
  Edit: removing my comment, I misunderstood.
  - WJW 5y ago
    Not so, since the fact that it is in the range does not mean it will steadily go downwards. It might have numbers much bigger than the maximum value for a uint128 somewhere in its Collatz sequence and it is possible (though unlikely) that one of those numbers modulo the maximum value for a uint128 is the original number again. (That is, the modulo operation might introduce loops that are not present in the normal Collatz sequence because mathematical integers don't overflow)