Почему этот цикл с плавающей точкой заканчивается на 1 000 000?

Question

Ответ на этот пример домашней задачи - «1 000 000», но я не понимаю, почему:

Что выводит следующий код?

int main(void) {
  float k = 1;
  while (k != k + 1) {
    k = k + 1;
  }
  printf(“%g”, k); // %g means output a floating point variable in decimal
}

Если программа работает бесконечно, но ничего не выводит, напишите INFINITE LOOP в качестве ответа на вопрос. Все программы компилируются и запускаются. Однако они могут содержать или не содержать серьезных ошибок. Вы должны предположить, что int составляет четыре байта. Вы должны предположить, что float имеет эквивалент шести десятичных цифр точности. Вы можете округлить свой ответ до ближайшей степени 10 (например, вы можете сказать 1000 вместо 2 ¹⁰ (т.е. 1024)).

Я не понимаю, почему цикл вообще завершится.

Answer 1

Он не работает вечно по той простой причине, что числа с плавающей запятой не идеальны.

В какой-то момент, k станет достаточно большим, так что добавление 1 к нему не будет иметь никакого эффекта.

В этот момент k будет равен k+1, и ваш цикл завершится.

Числа с плавающей запятой могут различаться по одной единице, только когда они находятся в определенном диапазоне.

В качестве примера предположим, что у вас есть целочисленный тип с точностью до 3 десятичных цифр для положительного целого числа и показатель с одним десятичным знаком.

При этом вы можете идеально представить числа от 0 до 999 как 000x10 ⁰ до 999x10 ⁰ (поскольку 10 ⁰ равно 1):

Что происходит, когда вы хотите представлять 1000? Вам нужно использовать 100x10 ¹ . Это по-прежнему отображается отлично.

Однако, существует нет точного способа представления 1001 с помощью этой схемы, следующее число, которое вы можете представить, это 101x10 ¹ , что равно 1010.

Таким образом, когда вы добавляете 1 к 1000, вы получите ближайшее совпадение, равное 1000.

Answer 2

В коде используется переменная float.

Как указано в вопросе, float имеет 6 цифр точности, что означает, что любые цифры после шестой будут неточными.Следовательно, после того, как вы передадите миллион, последняя цифра будет неточной, так что ее увеличение не может иметь никакого эффекта.

Answer 3

Вывод этой программы не указан стандартом C, так как семантика типа float не указана. Один вероятный результат (то, что вы получите на платформе, для которой float арифметика оценивается с одинарной точностью IEEE-754) - 2^24.

Все целые числа, меньшие 2^24, точно представлены в одинарной точности, поэтому вычисления не остановятся до этой точки. Следующее представимое число с одинарной точностью после 2^24, однако, равно 2^24 + 2. Поскольку 2^24 + 1 находится точно посередине между этим числом и 2^24, в стандартном режиме округления IEEE-754 он округляется до того, у которого завершающий бит равен нулю, то есть 2^24.

Другие вероятные ответы включают 2^53 и 2^64. Возможны и другие ответы. Infinity (значение с плавающей запятой) может привести к платформе, для которой режим округления по умолчанию, например, округляется. Как отмечали другие, бесконечный цикл также возможен на платформах, которые оценивают выражения с плавающей точкой в ​​более широком типе (который является источником всевозможной путаницы программиста, но допускается стандартом C).

Answer 4

На самом деле, на большинстве компиляторов C это будет выполняться вечно (бесконечный цикл), хотя точное поведение определяется реализацией.

Причина, по которой большинство компиляторов дают бесконечный цикл, заключается в том, что они оценивают все выражения с плавающей запятой с точностью double и только округляют значения до float (single) с точностью при сохранении в Переменная. Поэтому, когда значение k достигает примерно 2 ^ 24, k == k + 1 все равно будет оцениваться как ложное (поскольку double может содержать значение k + 1 без округления), но присвоение k = k + 1 будет noop, так как k + 1 должно быть округлено, чтобы поместиться в поплавок

1012 * редактировать *

gcc на x86 получает это поведение бесконечного цикла. Интересно, что на x64 это не так, поскольку он использует инструкции sse, которые выполняют сравнение с плавающей точностью.