### On overflow errors

I was asked to create a simplified shortest-path generator.

"Simplified" meaning, in this case, "On every step go from the current point to the nearest unvisited point", which is, fortunately, just O(n^2), not NP-hard.

Now, the sample data I was given consists of 13312 points, spread out in a circle of radius ~45000. I spent a little time determining that attempting to calculate Euclidean distances between any two points could result in a 32-bit integer overflow, so I very carefully used 64-bit integers (uint64), as follows:

I didn't, until I trimmed the data-set down to only ~5k points, and pinned down the exactly which point caused the "nearest" algorithm to skip to the other side of the disk, and watched exactly what happened.

If you are still looking for the bug, quit reading until you give up.

The bug? At that point, the square of the distance from the current point to the next point was then about 4.30 billion. Unsigned 32-bit integer overflow happens at about 4.29 billion. And that fifth statement is missing the all-important casts to make it 64-bit multiplication and addition, instead of 32-bit. So, instead of assigning 4.3 billion, it helpfully assigned 10 million. And things proceeded to go downhill from there.

Does anyone have a DWIM module[0] I can borrow? And no, not interested in ACME::DWIM or Parrot::DWIM.[1] Those are for Perl, which doesn't help me much here.

[0] You're on the Internet; look it up!

[1] You're on the Internet; loo^H^H^Hyou're better off not knowing.

"Simplified" meaning, in this case, "On every step go from the current point to the nearest unvisited point", which is, fortunately, just O(n^2), not NP-hard.

Now, the sample data I was given consists of 13312 points, spread out in a circle of radius ~45000. I spent a little time determining that attempting to calculate Euclidean distances between any two points could result in a 32-bit integer overflow, so I very carefully used 64-bit integers (uint64), as follows:

uint64 distsquared; /*...*/ uint deltax = abs(point[j].x - point[i].x), deltay = abs(point[j].y - point[i].y); if(((uint64(deltax))*deltax + (uint64(deltay))*deltay) < distsquared){ distsquared = deltax*deltax + deltay*deltay; /* Other stuff */ }Anyone spotted the problem there yet?

I didn't, until I trimmed the data-set down to only ~5k points, and pinned down the exactly which point caused the "nearest" algorithm to skip to the other side of the disk, and watched exactly what happened.

If you are still looking for the bug, quit reading until you give up.

The bug? At that point, the square of the distance from the current point to the next point was then about 4.30 billion. Unsigned 32-bit integer overflow happens at about 4.29 billion. And that fifth statement is missing the all-important casts to make it 64-bit multiplication and addition, instead of 32-bit. So, instead of assigning 4.3 billion, it helpfully assigned 10 million. And things proceeded to go downhill from there.

Does anyone have a DWIM module[0] I can borrow? And no, not interested in ACME::DWIM or Parrot::DWIM.[1] Those are for Perl, which doesn't help me much here.

[0] You're on the Internet; look it up!

[1] You're on the Internet; loo^H^H^Hyou're better off not knowing.