7 ms·
Collatz conjecture is tested to be true for n < 2^100000 - 1. That is, true for all value represent-able in usize.
by j16sdiz 3y ago
Collatz conjecture is tested to be true for n < 2^100000 - 1.
That is, true for all value represent-able in usize.
- Squeeze2664 3y agoSounds like it was working as intended, then! Doing a great job at it, too.
- dllthomas 3y agoSounds, rather, like it was doing the right thing in that case but for the wrong reasons!
- Sharlin 3y agoOh yes, that's just LLVM's ConstantFoldCollatzConjecture pass, a basic optimization. > That is, true for all value represent-able in usize. A slight understatement!
- dllthomas 3y agoBut exactly the statement you need to fold it to a constant.
- not2b 3y agoBut if we pass in an odd value that is more than half of the maximum value represented in a usize, we get an overflow and a panic when we make a recursive call with n * 3 + 1, right? We shouldn't be optimizing those away.
- kevincox 3y agoIn the default release profile math wraps.
- progbits 3y agoBut does it converge using wrapping math for all usize values? There might be a cycle in theory.
- kevincox 3y agoThere can be a cycle but IIRC Rust inherits C/C++'s rule that infinite loops without side effects are undefined behaviour. So there are cycles (for example 0) but since there are no side effects and the only way to escape the loop is the `return true` the compiler only has to handle the `return true` path.
- progbits 3y agoOh sure that is fine, I just wonder if colatz is proven to converge for 32bit/64bit wrapping integer math.