0x5f3759df
Брзи инверз квадратног корена (познат и као -{Fast InvSqrt()}- или по хексадекадној константи -{0x5f3759df}-) је метод за рачунање x−½, мултипликативног инверза квадратног корена броја записаног у 32-битној прецизности покретног зареза у IEEE 754 формату. Алгоритам је вероватно развијен у компанији Силикон графикс почетком 1990-их, а његова имплементација се јавила 1999. у изворном коду игрице -{Quake III Arena}-, али сам метод се није појавио на јавним форумима као што је -{Usenet}- све до 2002 или 2003.[1] У то време, првенствена предност алгоритма се састојала у избегавању рачунски скупих аритметичких операција у покретном зарезу, уместо којих се користе целобројне операције. Инверзни квадратни корен се користи у рачунању упадних углова и рефлексије светлости и сенки у рачунарској графици.
Алгоритам узима 32-битни број у покретном зарезу као улаз, и складишти његову половину за каснију употребу. Затим се, посматрајући битове који представљају број у покретном зарезу као 32-битни цео број, спроводи операција логичког шифтовања удесно за један бит, а резултат те операције се одузима од „магичне“ константе -{0x5f3759df}-. Ово је прва апроксимација инверзног квадратног корена улаза. Затим се битови поново посматрају као број у покретном зарезу и спроводи се једна итерација Њутновог метода како би се добила прецизнија апроксимација. Ово рачуна апроксимацију инверза квадратног корена броја у покретном зарезу отприлике четири пута брже него коришћењем дељења бројева у покретном зарезу.
Алгоритам је првобитно приписиван Џону Кармаку, али је истраживање показало да овај код има дубље корене у хардверској и софтверској страни рачунарске графике. Прилагођавања и измене су пролазиле кроз компаније Силикон графикс и -{3dfx Interactive}-, а имплементација Гарија Таролија за -{SGI Indigo}- представља најранију познату употребу алгоритма. Није познато како је константа првобитно откривена, мада је истраживање навело на неке могуће методе.
Мотивација
Инверз квадратног корена броја у покретном зарезу се користи у рачунању нормализованог вектора.Шаблон:Sfn Како програми који раде са 3Д графиком користе ове нормализоване векторе за одређивање осветљења и рефлексија, неопходно је извршити милионе оваквих рачунања у секунди. Пре него што је развијен специјализовани хардвер који се бави трансформацијама и осветљењем, софтверско израчунавање је могло да буде врло споро. Конкретно, када је овај алгоритам развијен раних 1990-их, већина процесора је била много спорија у рачунању операција са покретним зарезом него у рачунању целобројних операција.[1]
Како би се нормализовао вектор, одређује се дужина вектора рачунањем његове еуклидске норме: квадратни корен збира квадрата координата вектора. Када се свака координата вектора подели том дужином, вектор постаје јединични вектор са истим правцем.
- је еуклидска норма вектора, аналогна еуклидском растојању између две тачке у еуклидском простору.
- је нормализовани (јединични) вектор. Ако се са представи , добије се
- , што повезује јединични вектор са инверзом квадратног корена компоненти раздаљине.
-{Quake III Arena}- је користила алгоритам за брзи инверз квадратног корена како би убрзала израчунавање у графичкој процесној јединици, али овај алгоритам је у међувремену имплементиран у специјалним хардверским вертекс шејдерима који користе -{FPGA}-.[2]
Преглед кода
Следи изворни код имплементације алгоритма за брзи инверз квадратног корена коришћен у игрици -{Quake III Arena}-, са уклоњеним C препроцесорским директивама, али са очуваним неизмењеним оригиналним коментарима:Шаблон:Чињеница
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;
}
Како би се одредио инверз квадратног корена, полази се од апроксимације за , коју одређује софтвер, а затим се примењује нека нумеричка метода да би се апроксимација поправљала све док не дође у опсег прихватљивог одступања од тачног решења. Уобичајени софтверски методи са почетка 1990-их су прву апроксимацију извлачили из предефинисаних таблица.Шаблон:Sfn Горенаведени код се у пракси показао бржим од таблица, и отприлике четири пута бржи него кад би се користило уобичајено дељење у покретном зарезу.[3] Долазило је до извесног губитка у прецизности, али је он надомешћен значајним напретком у перформансама.[4] Алгоритам је развијен за -{IEEE 754-1985}- 32-битне бројеве у покретном зарезу, али испитивање Криса Ломонта и касније Чарлса МакЕнирија је показало да би могао да буде имплементиран и у другим форматима бројева у покретном зарезу.
Предности у брзини које пружа овај алгоритам се између осталог заснивају на „досетки“ да се 32-битни број у покретном зарезу[note 1] третира као цео број и одузме од специфичне константе, -{0x5f3759df}-. Сврха константе није одмах јасна некоме ко прегледа код, па се стога, као и друге сличне константе које се користе у програмирању, често назива „магичним бројем“.[1]Шаблон:SfnШаблон:Sfn[5] Ово целобројно одузимање и битовско шифтовање даје 32-битну вредност која се затим поново посматра као број у покретном зарезу, и представља грубу апроксимацију инверза квадратног корена почетног броја. Примењује се једна итерација Њутновог метода како би се добило на прецизности, и ту се код завршава. Алгоритам генерише разумно прецизне резултате користећи јединствену прву апроксимацију за Њутнов метод. Међутим, ово је знатно спорије и мање прецизно него коришћење -{SSE}- инструкције rsqrtss на x86 процесорима, која је такође објављена 1999.[6]
Напомене
- ↑ Коришћење типа
longумањује портабилност овог кода на модерним системима. Како би се код извршавао исправно,sizeof(long)мора да буде 4 бајта, у супротном може да дође до негативних вредности у резултату. На многим модерним 64-битним системима,sizeof(long)је 8 бајтова.