Исправлен алгоритм обратного квадратного корня Carmack/Welsh

Question

При реализации "Carmack's Inverse Square Root" algorithm я заметил, что результаты кажутся предвзятыми. Этот код дает лучшие результаты:

float InvSqrtF(float x) 
{ 
    // Initial approximation by Greg Walsh. 
    int i = * (int*) &x; 
    i = 0x5f3759df - (i >> 1); 
    float y = * (float *) &i; 
    // Two iterations of Newton-Raphson's method to refine the initial estimate. 
    x *= 0.5f; 
    float f = 1.5F; 
    y = y * (f - (x * y * y)); 
    y = y * (f - (x * y * y)); 
    * (int *)(&y) += 0x13; // More magic. 
    return y; 
} 

Главное отличие в предпоследней «более волшебной» линии. Поскольку исходные результаты были слишком низкими с помощью довольно постоянного коэффициента, это добавляет 19 * 2^(показатель (y) -bias) к результату только с одной инструкцией. Кажется, мне дают около 3 дополнительных бит, но я что-то пропускаю?

Answer 1

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

f(y) = x - 1/y² 

является вогнутой, так что - если не начать с y ≥ √(3/x) - метод Ньютона только производит приближения ≤ 1/√x (и строго меньше, если не начать с точным результатом) с точным арифметика.

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

Да, есть предвзятость, и добавление небольшого количества обычно улучшает результат. Но не всегда. Например, в области около 1,25 или 0,85 результаты без корректировки лучше, чем с. В других регионах настройка дает один бит дополнительной точности, а в других - больше.

В любом случае, добавленная магическая константа должна быть скорректирована в область, из которой x чаще всего берется за лучший результат.

Answer 2

Поскольку этот метод является приблизительным, результат будет несколько завышен и недооценен некоторыми другими. Вы можете найти на McEniry's paper некоторые интересные цифры о том, как эта ошибка распространяется для разных конфигураций, и математика позади них.

Итак, если у вас есть твердые доказательства того, что в вашей области применения результат явно предвзятым, я предпочел бы настраивая волшебную константу, как предложено в Lomont's document :-)