Timeline for Collatz sequence in C
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2023 at 18:49 | history | edited | chux | CC BY-SA 4.0 |
added 91 characters in body
|
| Jun 12, 2023 at 9:21 | comment | added | fudo | "If you can optimize better than the compiler, get a better compiler." this should be told in class. | |
| Jun 11, 2023 at 2:36 | comment | added | Peter Cordes |
Oh, I read the question more carefully and see they are actually playing with negative starting values for the sequence. In general x/2 (truncating toward zero) is not equivalent to x>>1 (rounding toward -inf), but interestingly in this case it's only done on even numbers, so either works. But GCC and clang don't notice that, and do the full rounding correction using shr reg, 63 / add before sar: godbolt.org/z/osT5c94Ph So your version is less efficient. x*3+1 is good, though; compilers know how to split it into x*2 + x for an x86 LEA, no need to do that manually.
|
|
| Jun 11, 2023 at 2:25 | comment | added | Peter Cordes |
Using x/2 instead of x>>1 would make the code slower unless you also change x from long long to unsigned long long. See Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?. That would also sidestep the whole %2 issue @TobySpeight discussed. (Although compilers are smart enough to optimize x%2 != 0 the same as x&1 even for signed types, the problem is only when code insists on writing x%2 == 1 that forces compilers to make asm such that it's false for negative odd integers.)
|
|
| Jun 10, 2023 at 16:45 | comment | added | chux |
@TobySpeight Agree that if (x%2) is like if (x&1) if x in unsigned or signed (aside from the so to be gone non- 2's complement). IAC, mod and signed % are a general source of errors given -1%2 --> -1.
|
|
| Jun 10, 2023 at 13:23 | vote | accept | nyz | ||
| Jun 10, 2023 at 7:46 | comment | added | Toby Speight |
Do you say that x%2 is not the same as mathematical x mod 2 because the result is different for negative numbers? Whilst that's true in general, we're in a boolean context here (i.e. implicitly x&2 != 0), for which the result should be the same, and a compiler may be able to produce identical code (though I haven't confirmed that the ones I care about actually do).
|
|
| Jun 10, 2023 at 4:00 | history | edited | chux | CC BY-SA 4.0 |
added 23 characters in body
|
| Jun 10, 2023 at 3:52 | history | edited | chux | CC BY-SA 4.0 |
added 113 characters in body
|
| Jun 10, 2023 at 3:47 | history | edited | chux | CC BY-SA 4.0 |
added 113 characters in body
|
| Jun 10, 2023 at 3:27 | history | answered | chux | CC BY-SA 4.0 |