News for hackers. Stuff that matters.

A comment on “Pack it in, mathematicians, someone owes LLVM a million bucks”. Parent comment

Re:“Pack it in, mathematicians, someone owes LLVM a million ... by WJW on Thursday August 19, 2021 @10:17AM (#28234128)
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.

[ Parent | on HN ]
Re:“Pack it in, mathematicians, someone owes LLVM a million ... by ludocode on Thursday August 19, 2021 @11:13AM (#28234880)
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.
[ Parent | on HN ]
Re:“Pack it in, mathematicians, someone owes LLVM a million ... by plasticchris on Thursday August 19, 2021 @11:33AM (#28235153)
Edit: removing my comment, I misunderstood.
[ Parent | on HN ]
Re:“Pack it in, mathematicians, someone owes LLVM a million ... by WJW on Thursday August 19, 2021 @11:40AM (#28235247)
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)
[ Parent | on HN ]