check for uint64_t overflow in a loop

Question

I have a C-method which calculates the k-th number of the collatz-sequence of n.

If n is / gets bigger than 64-Bit the method may return 0.

My approach however has a lot of false positives. How can a check for an 64 Bit overflow better?

uint64_t collatz_K(uint64_t n, uint64_t k) {

    while (k>0){

        if(n > (UINT64_MAX / 3)-1){
           return 0;                   // check if overflow occurs.
        } if(n==1 && k%2==0){
           break;                      //premature break of the method if the end of the sequence is reached.
        }
        else{
            if(n%2 == 0){
                n = n >> 1;
            }else {
                n = 3*n +1;
            }                
            k--;
        }
    }
    return n;    
}

You need to move your check before making the problematic calculation that is into the nested `else` clause. Because in the other cases there is no danger of overflow. — Eugene Sh., Apr 26 '23 at 14:26
Please read my answer https://stackoverflow.com/a/46442848/7733418 on a similar question. I think it might help you (without actually proposing that it is a duplicate of this question). — Yunnosch, Apr 26 '23 at 14:32
Off-topic, but I'd say poor formatting style... 1. If one of if/else (or a chain of) needs parentheses I strongly recommend adding to all of. 2. as you `break` within the if anyway I wouldn't add an `else` at all (some consider doing so bad style but that's debatable...). Now just a matter of personal taste (really?), but I personally would prefer `for(;k > 0; --k)` – no change of control flow, but the actual loop parts aren't scattered around code. — Aconcagua, Apr 26 '23 at 14:50
@HeapUnderStop Off topic, why do you check for `n==1 && k%2==0`? Isn't it enough to check for `n==1`? It's at least what I see here: https://en.wikipedia.org/wiki/Collatz_conjecture — vvv444, Apr 26 '23 at 15:12
Logically `(UINT64_MAX / 3) - 1` ought to be `(UINT64_MAX - 1) / 3`, but it doesn't matter because the value is the same for integer division (because `UINT64_MAX` is divisible by 3, as is 2^(2n)-1 for n∈ℤ⁺). — Ian Abbott, Apr 26 '23 at 15:48

vvv444 · Accepted Answer · 2023-04-26T17:11:14.660

3

You should do two things:

Apply the check for overflow only in the case when you calculate 3*n+1.
Use n > (UINT64_MAX - 1) / 3 instead of n > (UINT64_MAX / 3) - 1.

uint64_t collatz_K(uint64_t n, uint64_t k) {
    for (; k>0; --k) {
        if (n==1 && k%2==0) {
           break; // premature break of the method if the end of the sequence is reached.
        }
        
        if(n%2 == 0){
            n = n >> 1;
        } else {
            if (n > (UINT64_MAX - 1) / 3)
                return 0; // Overflow will occur
            
            n = 3*n + 1;
        }                
    }
    return n;    
}

If your multiplication factor wasn't a compile-time constant (3) but something known only in runtime, you could have used one of the other overflow check approaches suggested here.

edited Apr 26 '23 at 17:11

answered Apr 26 '23 at 15:36

vvv444

2,764
1
14
25

A third approach is to check for overflow before the operation, as was done in OP's original code (but in the wrong place; it should have been done in the `else` part). Admittedly, that was one of the answers in the question you linked, but it's better if the division is done at compile time as in OP's original code. – Ian Abbott Apr 26 '23 at 16:27
@IanAbbott Actually, you are right. Since the multiply factor is hard-coded, it's enough to check in compile time. All he had to do is moving the check. – vvv444 Apr 26 '23 at 17:05
I've completely revamped the answer. – vvv444 Apr 26 '23 at 17:20

check for uint64_t overflow in a loop

1 Answers1