Почему "быстрый обратный квадратный корень" медленнее, чем 1/sqrt() при очень большом float?

Question

Следующий полный код может сравнивать скорость быстрого обратного квадратного корня с 1/sqrt(). Согласно этому предложению в википедии (т.е. алгоритм был примерно в четыре раза быстрее, чем вычисление квадратного корня другим методом и вычисление обратной величины с помощью деления с плавающей запятой.)

Но вот почему я здесь: он медленнее, чем 1/sqrt(). что-то не так в моем коде? Пожалуйста.

    #include <stdio.h>
    #include <time.h>
    #include <math.h>

    float FastInvSqrt (float number);

    int
    main ()
    {
      float x = 1.0e+100;

      int N = 100000000;
      int i = 0;

      clock_t start2 = clock (); 
      do  
        {   
          float z = 1.0 / sqrt (x);
          i++;
        }   
      while (i < N); 
      clock_t end2 = clock (); 

      double time2 = (end2 - start2) / (double) CLOCKS_PER_SEC;

      printf ("1/sqrt() spends %13f sec.\n\n", time2);

      i = 0;
      clock_t start1 = clock (); 
      do  
        {   
          float y = FastInvSqrt (x);
          i++;
        }   
      while (i < N); 
      clock_t end1 = clock (); 

      double time1 = (end1 - start1) / (double) CLOCKS_PER_SEC;



      printf ("FastInvSqrt() spends %f sec.\n\n", time1);


      printf ("fast inverse square root is faster %f times than 1/sqrt().\n", time2/time1);

      return 0;
}

float
FastInvSqrt (float x)
{
  float xhalf = 0.5F * x;
  int i = *(int *) &x;  // store floating-point bits in integer
  i = 0x5f3759df - (i >> 1);    // initial guess for Newton's method
  x = *(float *) &i;            // convert new bits into float
  x = x * (1.5 - xhalf * x * x);        // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  return x;
}

Результат выглядит следующим образом:

1/sqrt() spends      0.850000 sec.

FastInvSqrt() spends 0.960000 sec.

fast inverse square root is faster 0.885417 times than 1/sqrt().

Answer 1

Функция, которая сокращает область, в которой она вычисляет с точностью, будет иметь меньшую вычислительную сложность (что означает, что ее можно вычислить быстрее). Это можно рассматривать как оптимизацию вычисления формы функции для подмножества ее определения или как алгоритмы поиска, каждый из которых лучше всего подходит для определенного типа входных данных (теорема о запрете бесплатного обеда).

Таким образом, использование этой функции для входных данных за пределами интервала [0, 1] (для которого, я полагаю, она была оптимизирована / предназначена) означает использование ее в подмножестве входных данных, где ее сложность хуже (выше), чем другие, возможно, специализированные варианты функций. которые вычисляют квадратные корни.

Функция sqrt(), которую вы используете из библиотеки, сама (вероятно) также была оптимизирована, поскольку она имеет предварительно вычисленные значения в своего рода LUT (которые действуют как начальные предположения для дальнейших приближений); использование такой более «общей функции» (что означает, что она охватывает большую часть домена и пытается повысить ее эффективность, например, с помощью предварительных вычислений; или устранение избыточных вычислений, но это ограничено; или максимизация повторного использования данных во время выполнения) имеет свою сложность ограничения, потому что чем больше вариантов выбора между предварительными вычислениями для интервала, тем больше накладных расходов на принятие решения; поэтому знание во время компиляции, что все ваши входные данные в sqrt находятся в интервале [0, 1], поможет уменьшить накладные расходы времени выполнения,поскольку вы заранее знаете, какую специализированную функцию приближения использовать (или вы можете сгенерировать специализированные функции для каждого интересующего интервала во время компиляции -> см. метапрограммирование для этого).

Answer 2

Я исправляю свой код следующим образом: 1. вычисляю случайное число вместо фиксированного числа. 2. посчитайте время, потраченное внутри цикла, и суммируйте его.

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>

float FastInvSqrt (float number);

int
main ()
{
  float x=0;
  time_t t;

  srand((unsigned) time(&t));

  int N = 1000000;
  int i = 0;

  double sum_time2=0.0;

  do  
    {   
      x=(float)(rand() % 10000)*0.22158;
  clock_t start2 = clock (); 
      float z = 1.0 / sqrt (x);
  clock_t end2 = clock (); 
        sum_time2=sum_time2+(end2-start2);
      i++;
    }   
  while (i < N); 


  printf ("1/sqrt() spends %13f sec.\n\n", sum_time2/(double)CLOCKS_PER_SEC);

  double sum_time1=0.0;

  i = 0;
  do  

    {
      x=(float)(rand() % 10000)*0.22158;
  clock_t start1 = clock ();
      float y = FastInvSqrt (x);
  clock_t end1 = clock ();
        sum_time1=sum_time1+(end1-start1);
      i++;
    }
  while (i < N);

  printf ("FastInvSqrt() spends %f sec.\n\n", sum_time1/(double)CLOCKS_PER_SEC);

  printf ("fast inverse square root is faster %f times than 1/sqrt().\n", sum_time2/sum_time1);

  return 0;
}

float
FastInvSqrt (float x)
{
  float xhalf = 0.5F * x;
  int i = *(int *) &x;  // store floating-point bits in integer
  i = 0x5f3759df - (i >> 1);    // initial guess for Newton's method
  x = *(float *) &i;            // convert new bits into float
  x = x * (1.5 - xhalf * x * x);        // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  //x = x * (1.5 - xhalf * x * x);      // One round of Newton's method
  return x;
}

но быстрый обратный квадратный корень все еще медленнее, чем 1/sqrt().

1/sqrt() spends      0.530000 sec.

FastInvSqrt() spends 0.540000 sec.

fast inverse square root is faster 0.981481 times than 1/sqrt().