Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

численные методы

Исследование одного очень красивого хака (PDF, англ.) - быстрого вычисления функции 1/sqrt(x) (обратный квадратный корень):

float InvSqrt(float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;       // get bits for floating value
    i = 0x5f3759df - (i>>1); // gives initial guess 
    x = *(float*)&i;         // convert bits back to float
    x = x*(1.5f-xhalf*x*x);  // Newton step, repeating increases accuracy
    return x;
}

Статья объясняет, почему и как это работает, и откуда взялась таинственная магическая константа 0x5f3759df.

Очень красиво.

Кстати, если не ошибаюсь, при чтении этого кода и этой статьи мне впервые понадобилось вообще для чего-либо знание метода приближений Ньютона, с тех пор, как я его выучил на курсе численных методов в университете 12 лет назад.

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 21 comments