Clang Solves the Collatz Conjecture? | Hacker News Reader

Clang Solves the Collatz Conjecture?

godbolt.org

14 pointssigna1111 comments

The 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), it seems to be invalid.

I 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.

> 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.

There's only of the order of a billion values to check. It's known to be true for all those values.

Same essential issue as "C Compilers Disprove Fermat’s Last Theorem" ?

https://blog.regehr.org/archives/140

https://news.ycombinator.com/item?id=1310105

Or is this one because "unsigned int" is not the same as a [0...infinity) "Integer" ?

The 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?

I 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?

This 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/ub#Infinite_loop_...

Oh, right. I knew the "eventually must" rule, but missed the implication.

It 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.

Yeah, it's solved for "unsigned int". Solving it for all integers is a little tougher...

Reply on news.ycombinator.com