Ищите канонический пример этой проблемы переполнения

Question

Это недавно появилось в интервью (концепция), и сегодня я обсуждал это с другом. Вот идея:

Предположим, вы вычисляете скалярное произведение трехмерного вектора. Простая функция: «return (x1 * x2) + (y1 * y2) + (z1 * z2)».

Однако, если первое и второе слагаемые являются большими положительными числами, они могут переполниться, даже если они ответят в пределах допустимого диапазона. Например, допустим, что целочисленный предел равен 128. 100 + 100 - 80 = 120, но если вы сделаете первые два добавления первыми, вы переполнитесь.

В университетском классе это было сделано для задания на С, где мы вычисляли то, что мы, вероятно, делали тысячу раз раньше, но никогда не обращали внимания на переполнение (это была часть, когда мы учились писать санитарный кодекс) как взятие среднего или что-то в этом роде.

Кто-нибудь знает, в каком контексте это могло произойти? Я знаю, что в какой-то ситуации вам приходилось использовать сравнения до или вместо сложения / вычитания, чтобы избежать этого переполнения

Answer 1

Двоичный поиск - классический пример.Многие реализации реализуют вычисления, которые в основном находят среднюю точку двух индексов: (высокий + низкий) / 2, но если высокие и низкие значения близки к Integer.MAX_VALUE или эквиваленту для вашего языка, переполнение высоких + низких значений до того, как произойдет делениеи ваш ответ неверен:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

В этом случае можно легко исправить: high / 2 + low / 2 вместо этого, который не переполняется, но это почти универсальная ошибкав реализациях бинарного поиска, и это самое первое, что приходит на ум, когда кто-то говорит о переполнении в вычислении, которое должно привести к непереполненному значению.