21:43 

O
Пау-чок
Вот то, о чём я и писал. "Проблема википедии".
Многим программистам известен довольно нетривиальный алгоритм приближённого вычисления "инверсного квадратного корня" - т.е. функции y(x)=1/sqrt(x). Ну, или по крайней мере известно о его существовании, а дальнейшее гуглится на раз.
Рассматривая возможность применения алгоритма применительно к флешу... В общем...

Функция "быстрого инверсного квадратного корня", как она представлена в коде Quake III, имеет вид:

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}


На первый взгляд вообще не понятно, как эта функция работает и почему результат вообще получается верным.
Основой алгоритма является строка, к которой кто-то из разработчиков id Software приписал вполне себе закономерный комментарий: "what the fuck?". Да, там происходит магия =) Но магия эта, как оказалось, вполне объяснима с математической точки зрения. Правда, что должно было упасть на голову изобретателю метода, чтобы начать мыслить в таком направлении, я даже представить не могу...

Покопавшись в нескольких гримуарах, описывающих ритуалы призвания магических чисел типа выше упомянутого 0x5f3759df, и кое-что даже усвоив, не смог устоять и попробовал скастовать что-то подобное.
Получилось не ахти, конечно. Т.к. с какого-то перепуга я решил приняться за функцию y(x)=1/x. Ну, подумалось мне, во флеше деление работает не ахти как быстро. А вдруг удастся ускорить?
В общем-то получилось вот что, дающее относительную погрешность не больше ±6.5e-4%.

float inline inv(float x){
union{
float f; //32 bit float
uint32_t i; //32 bit unsigned int
} y;
y.f=x;
y.i=0x7EF311C3-y.i;
y.f*=2-y.f*x;
y.f*=2-y.f*x;
return y.f;
}


Практической пользы от этой функции чуть меньше, чем никакой =) Она отрабатывает раза в два-три медленнее, чем простое деление =)
Однако же сам факт того, что можно получить число 1/x вообще не используя операцию деления, а лишь чуть-чуть пошаманив, меня весьма вдохновляет =)

@темы: программерское

URL
   

subject to change

главная