Почему подсчет до 2^24 выполняется быстро, но подсчет до 2^25 занимает намного больше времени?

Question

Я искал бесконечные циклы, чтобы проверить какой-то другой код/​​мое понимание, и наткнулся на это странное поведение. В приведенной ниже программе подсчет от 0 до 2^24 принимает < 100 мс на моей машине, но при подсчете до 2^25 на порядок больше времени (на момент написания, он все еще выполняется).

Почему это так?

Это было под Java 1.8.0_101, на 64-битной копии ОС Windows 10.

TestClass.java

public class TestClass { 
    public static void main(String[] args) { 
     addFloats((float) Math.pow(2.0, 24.0)); 
     addFloats((float) Math.pow(2.0, 25.0)); 
    } 

    private static void addFloats(float number) { 
     float f = 0.0f; 
     long startTime = System.currentTimeMillis(); 

     while(true) { 
      f += 1.0f; 
      if (f >= number) { 
       System.out.println(f); 
       System.out.println(number + " took " + (System.currentTimeMillis() - startTime) + " msecs"); 
       break; 
      } 
     } 
    } 
} 

Answer 1

Это потому, что float s имеют минимальную точность, которая может быть представлена, который уменьшился по мере увеличения значения float. Где-то между 2^24 и 2^25 добавление одного уже недостаточно, чтобы изменить значение на следующее наибольшее представимое число. В этот момент, каждый раз через цикл, f просто сохраняет одно и то же значение, так как f += 1.0f больше не изменяет его.

Если вы измените петлю на это:

while(true) { 
    float newF = f + 1.0f; 
    if(newF == f) System.out.println(newF); 
    f += 1.0f; 
    if (f >= number) { 
     System.out.println(f); 
     System.out.println(number + " took " + (System.currentTimeMillis() - startTime) + " msecs"); 
     break; 
    } 
} 

Вы можете увидеть, как это происходит. Кажется, что он перестает расти, как только f достигает 2^24.

Выход этого кода будет бесконечным числом «1.6777216E7», если вы запустите его с помощью 2^25.

Вы можете проверить это значение, используя Math.nextAfter function, в котором указано следующее представляемое значение. Если вы попробуйте запустить этот код:

float value = (float)Math.pow(2.0, 24.0); 
System.out.println(Math.nextAfter(value, Float.MAX_VALUE) - value); 

вы можете увидеть, что следующее представимо значение после того, как 2^24 2^24 + 2.

За отличный пробой, почему это происходит, и почему он начинает что он делает, см. this answer