How to detect overflow in a function when n becomes greater than 64 bits?
uint64_t col(uint64_t n)
{
int count = 0;
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
n = (3 * n) + 1;
}
count++;
}
return count;
}
You can detect overflow, or more precisely wrap around, by comparing the value with a computed maximum before the operation:
#include <stdio.h>
#include <stdint.h>
uint64_t collatz(uint64_t n) {
uint64_t count = 0;
if (n == 0) {
return count;
}
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
if (n > (UINT64_MAX - 1) / 3) {
printf("overflow!\n");
return UINT64_MAX;
}
n = (3 * n) + 1;
}
if (count == UINT64_MAX) {
printf("too many iterations!\n");
return UINT64_MAX;
}
count++;
}
return count;
}
return 0; --> return UINT64_MAX; be better as an overflow sentinel value?
count can reach UINT64_MAX, it seems obvious that n must be part of a cycle that does not include 1, hence UINT64_MAX cannot be a legitimate result for a uint64_t argument.
n = (UINT64_MAX - 1) / 3, the computation will not overflow as the new value will be UINT64_MAX, UINT64_MAX-1 or UINT64_MAX-2, and the next value of n will produce UINT64_MAX+1, UINT64_MAX+2 or UINT64_MAX+3, hence an overflow. Using the exact values, n = 0x5555555555555554, 3 * n + 1 = 18446744073709551613, which is UINT64_MAX-2 and the next value produces UINT64_MAX+1 which wraps around to 0.The expression n /= 2; should never overflow, so I'm not worried about that.
The question I think you're asking is:
Will n = (3 * n) + 1; ever overflow?
That can be answered as an inequality:
(3 * n) + 1 > UINT64_MAX, then you have Overflow.And that is an inequality you can solve algebraically.
(3*n) > UINT64_MAX-1, then you have Overflown > (UINT64_MAX-1)/3, then you have OverflowSo, ultimately, if n > (UINT64_MAX-1)/3 (or approximately 6.1489e18), then you cannot complete the calculation without overflowing uint64_t.
