4 ms·
Clang Solves the Collatz Conjecture?
- wbhart 7y agoThere's only of the order of a billion values to check. It's known to be true for all those values.
- deleted 7y ago[deleted]
- jimws 7y agoThe interesting question is: Has someone "harcoded" a clever optimisation specifically for Collatz conjecture? Or did the general optimisation techniques figure this out of their own?
- Arnt 7y agoI looked at the source now and found nothing specific. The optimisation seems to be wrong; clang returns a constant 1, which assumes that the function is never called with n=0. Which is true for the Collatz conjecture (it starts at 1), but surely clang has no right to assume that n≥1?
- clmul 7y agoThis assumption is allowed, as n=0 results in infinite recursion (without side-effects) which is undefined behavior: https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/memory_model https://en.cppreference.com/w/cpp/language/ub#Infinite_loop_without_side-effects https://en.cppreference.com/w/cpp/language/ub#Infinite_loop_...
- Arnt 7y agoOh, right. I knew the "eventually must" rule, but missed the implication.
- ashearer 7y agoIt looks like a general optimization for tail-recursive functions that assumes they terminate (because not terminating would be undefined behavior). The parameters to the recursive calls don't matter: Substitute other expressions or constants for `n / 2` and `3 * n + 1`, and the compiled result remains the same. So it's not Collatz-specific. clang appears to correctly detect that `collatz` only directly defines a result for `1`, and any other input expands to yet another recursive call to `collatz` (the parameter is irrelevant). To avoid infinite recursion, `collatz` must eventually be called with the value 1, so that's what clang concludes.
- nwellnhof 7y agoThe function either returns 1 or loops infinitely. So if you assume that infinite loops are undefined behavior, the optimization is valid. I only know what the C11 standard says about infinite loops: > An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate. But this only applies to some iteration statements, not recursive functions. I don't know about C++ rules but since this optimization is also applied when compiling as C code (https://godbolt.org/z/K3uT2G https://godbolt.org/z/K3uT2G), it seems to be invalid.
- olliej 7y agoI believe infinite recursion is also UB, but alternatively if clang converts to a tail call, it can then be converted to a loop. If the loop is infinite then you’re back in UB land.
- nwellnhof 7y ago> if clang converts to a tail call, it can then be converted to a loop Yes, that's probably what happens internally. > If the loop is infinite then you’re back in UB land. I don't think so. At some point, clang forgets that the loop actually comes from a recursive function call, so it shouldn't be allowed to assume a finite loop.
- lacker 7y agoYeah, it's solved for "unsigned int". Solving it for all integers is a little tougher...
- papln 7y agoSame essential issue as "C Compilers Disprove Fermat’s Last Theorem" ? https://blog.regehr.org/archives/140 https://blog.regehr.org/archives/140 https://news.ycombinator.com/item?id=1310105 https://news.ycombinator.com/item?id=1310105 Or is this one because "unsigned int" is not the same as a [0...infinity) "Integer" ?