الگوریتم جذر چهار برابر سریعتر از الگوریتم های دیگر

[Direct-Man]

به نام خدا
در این پست قصد دارم که تا شما دوستان عزیز را با الگوریتم جذر که چهار برابر از الگوریتم معمولی سریعتر می باشد ، آشنا کنم . امیدوارم که مفید باشد.
این الگوریتم در بازی کمینگاه که از اینجا قابل دریافت است استفاده شده است . دلیل استفاده این الگوریتم در این بازی به ماهیت بازی و پلفترم آن بر می گردد و هدف ایجاد بازی بهینه بوده است .
تابع جذر در فاصله یابی بین دو نقطه، نرمال سازی بردار ها ، سایه زن ها برای نورپردازی و ... کاربرد زیادی دارد . الگوریتمی که در این پست به شما معرفی میشود موسوم به الگوریتم کارمک است که در بازی 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;                      
i  = 0x5f3759df - ( i >> 1 );              
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
return y;
}

این الگوریتم تابع عکس تابع sqrt(y) را با ثابت 0x5f3759df به صورت روش نیتون رافسون تقریب می زند و مقدار را بر میگرداند. نام دیگر این روش به جز روش کارمک روش fast_inverse_square_root می باشد.
این روش در بازی کمینگاه نیز استفاده شده است. شما می توانید این بازی را از مارکت کافه بازار دانلود نمایید.

​

امیدوارم این نکته مورد توجه شما قرار گرفته باشد .