5 ms·
The interesting question is: Has someone "harcoded" a clever optimisation specifically for Collatz conjecture? Or did the general optimisation techniques figure
by jimws 7y ago
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?
- 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.