Strange Error When Calculating Upper and Lower Bounds

Question

My program is multithreaded. Each thread is responsible for a certain chunk of data. What I'm doing is calculating a lower and upper bound then passing them into the thread function via a struct. Both lower_bound and upper_bound are unsigned integers.

The main thread has the following lower and upper bound.

lower_bound: 3;
upper_bound: (NUM/num_threads) - 1;

The other worker threads have the following lower and upper bounds.

lower_bound = (NUM * (i + 1))/(num_threads);
upper_bound = (NUM * (i + 2))/(num_threads) - 1;

NUM is a constant defined in my program. I've notice that the program works fine up to a certain order of magnitude. 10^8 works fine, but 10^9 doesn't. To debug my program I have the worker threads print off their output.

Output for 10 threads up to 10^8.

lower_bound: 10000000    upper_bound: 19999999
lower_bound: 20000000    upper_bound: 29999999
lower_bound: 30000000    upper_bound: 39999999
lower_bound: 60000000    upper_bound: 69999999
lower_bound: 70000000    upper_bound: 79999999
lower_bound: 50000000    upper_bound: 59999999
lower_bound: 80000000    upper_bound: 89999999
lower_bound: 40000000    upper_bound: 49999999
lower_bound: 90000000    upper_bound: 99999999

Output for 10 threads up to 10^9.

lower_bound: 100000000   upper_bound: 199999999
lower_bound: 200000000   upper_bound: 299999999
lower_bound: 300000000   upper_bound: 399999999
lower_bound: 70503270    upper_bound: 170503269
lower_bound: 170503270   upper_bound: 270503269
lower_bound: 270503270   upper_bound: 370503269
lower_bound: 370503270   upper_bound: 41006539
lower_bound: 41006540    upper_bound: 141006539
lower_bound: 400000000   upper_bound: 70503269

What in the world is going on?

Answer 1

Integer overflow. You have an unsigned 32-bit integer, which maxes out at little over 4 billion. After that it goes around and starts over at zero again.

Change to use a 64-bit integer instead (uint64_t or unsigned long long).