0x5f3759df

Израчунавања осветљења и рефлексија (овде приказани у пуцачини из првог лица *OpenArena*) користе брзи инверз квадратног корена за налажење упадног угла.

Брзи инверз квадратног корена (познат и као Fast InvSqrt() или по хексадекадној константи 0x5f3759df) је метод за рачунање x^−½, мултипликативног инверза квадратног корена броја записаног у 32-битној прецизности покретног зареза у IEEE 754 формату. Алгоритам је вероватно развијен у компанији Силикон графикс почетком 1990-их, а његова имплементација се јавила 1999. у изворном коду игрице Quake III Arena, али сам метод се није појавио на јавним форумима као што је Usenet све до 2002 или 2003.^[1] У то време, првенствена предност алгоритма се састојала у избегавању рачунски скупих аритметичких операција у покретном зарезу, уместо којих се користе целобројне операције. Инверзни квадратни корен се користи у рачунању упадних углова и рефлексије светлости и сенки у рачунарској графици.

Алгоритам узима 32-битни број у покретном зарезу као улаз, и складишти његову половину за каснију употребу. Затим се, посматрајући битове који представљају број у покретном зарезу као 32-битни цео број, спроводи операција логичког шифтовања удесно за један бит, а резултат те операције се одузима од „магичне“ константе 0x5f3759df. Ово је прва апроксимација инверзног квадратног корена улаза. Затим се битови поново посматрају као број у покретном зарезу и спроводи се једна итерација Њутновог метода како би се добила прецизнија апроксимација. Ово рачуна апроксимацију инверза квадратног корена броја у покретном зарезу отприлике четири пута брже него коришћењем дељења бројева у покретном зарезу.

Алгоритам је првобитно приписиван Џону Кармаку, али је истраживање показало да овај код има дубље корене у хардверској и софтверској страни рачунарске графике. Прилагођавања и измене су пролазиле кроз компаније Силикон графикс и 3dfx Interactive, а имплементација Гарија Таролија за SGI Indigo представља најранију познату употребу алгоритма. Није познато како је константа првобитно откривена, мада је истраживање навело на неке могуће методе.

Мотивација

Инверз квадратног корена броја у покретном зарезу се користи у рачунању нормализованог вектора.^[2] Како програми који раде са 3Д графиком користе ове нормализоване векторе за одређивање осветљења и рефлексија, неопходно је извршити милионе оваквих рачунања у секунди. Пре него што је развијен специјализовани хардвер који се бави трансформацијама и осветљењем, софтверско израчунавање је могло да буде врло споро. Конкретно, када је овај алгоритам развијен раних 1990-их, већина процесора је била много спорија у рачунању операција са покретним зарезом него у рачунању целобројних операција.^[1]

Како би се нормализовао вектор, одређује се дужина вектора рачунањем његове еуклидске норме: квадратни корен збира квадрата координата вектора. Када се свака координата вектора подели том дужином, вектор постаје јединични вектор са истим правцем.

\|{\boldsymbol {v}}\|={\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}

је еуклидска норма вектора, аналогна еуклидском растојању између две тачке у еуклидском простору.

{\boldsymbol {\hat {v}}}={\boldsymbol {v}}/\|{\boldsymbol {v}}\|

је нормализовани (јединични) вектор. Ако се са

{\boldsymbol {x}}

представи

v_{1}^{2}+v_{2}^{2}+v_{3}^{2}

, добије се

{\boldsymbol {\hat {v}}}={\boldsymbol {v}}/{\sqrt {x}}

, што повезује јединични вектор са инверзом квадратног корена компоненти раздаљине.

Quake III Arena је користила алгоритам за брзи инверз квадратног корена како би убрзала израчунавање у графичкој процесној јединици, али овај алгоритам је у међувремену имплементиран у специјалним хардверским вертекс шејдерима који користе FPGA.^[3]

Преглед кода

Следи изворни код имплементације алгоритма за брзи инверз квадратног корена коришћен у игрици 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;
}

Како би се одредио инверз квадратног корена, полази се од апроксимације за $x^{-1/2}$ , коју одређује софтвер, а затим се примењује нека нумеричка метода да би се апроксимација поправљала све док не дође у опсег прихватљивог одступања од тачног решења. Уобичајени софтверски методи са почетка 1990-их су прву апроксимацију извлачили из предефинисаних таблица.^[4] Горенаведени код се у пракси показао бржим од таблица, и отприлике четири пута бржи него кад би се користило уобичајено дељење у покретном зарезу.^[5] Долазило је до извесног губитка у прецизности, али је он надомешћен значајним напретком у перформансама.^[6] Алгоритам је развијен за IEEE 754-1985 32-битне бројеве у покретном зарезу, али испитивање Криса Ломонта и касније Чарлса МакЕнирија је показало да би могао да буде имплементиран и у другим форматима бројева у покретном зарезу.

Предности у брзини које пружа овај алгоритам се између осталог заснивају на „досетки“ да се 32-битни број у покретном зарезу^{[note 1]} третира као цео број и одузме од специфичне константе, 0x5f3759df. Сврха константе није одмах јасна некоме ко прегледа код, па се стога, као и друге сличне константе које се користе у програмирању, често назива „магичним бројем“.^[1]^[7]^[8]^[9] Ово целобројно одузимање и битовско шифтовање даје 32-битну вредност која се затим поново посматра као број у покретном зарезу, и представља грубу апроксимацију инверза квадратног корена почетног броја. Примењује се једна итерација Њутновог метода како би се добило на прецизности, и ту се код завршава. Алгоритам генерише разумно прецизне резултате користећи јединствену прву апроксимацију за Њутнов метод. Међутим, ово је знатно спорије и мање прецизно него коришћење SSE инструкције rsqrtss на x86 процесорима, која је такође објављена 1999.^[10]

Напомене

^ Коришћење типа long умањује портабилност овог кода на модерним системима. Како би се код извршавао исправно, sizeof(long) мора да буде 4 бајта, у супротном може да дође до негативних вредности у резултату. На многим модерним 64-битним системима, sizeof(long) је 8 бајтова.

Референце

^ ^а ^б ^в Sommefeldt, Rys (29. 11. 2006). „Origin of Quake3's Fast InvSqrt()”. Beyond3D. Приступљено 12. 02. 2009.
^ Blinn 2003, стр. 130.
^ Middendorf, Lars; Mühlbauer, Felix; Umlauf, George; Bodba, Christophe (01. 6. 2007). „Embedded Vertex Shader in FPGA”. Ур.: Rettberg, Achin. Embedded System Design: Topics, Techniques and Trends. IFIP TC10 Working Conference:International Embedded Systems Symposium (IESS). et al. Irvine, California: Springer. стр. 155—164. ISBN 978-0-387-72257-3.
^ Eberly 2001, стр. 504.
^ Lomont, Chris (2003). „Fast Inverse Square Root” (PDF). стр. 1. Приступљено 13. 02. 2009.
^ McEniry, Charles (2007). „The Mathematics Behind the Fast Inverse Square Root Function Code” (PDF). стр. 1. Архивирано из оригинала (PDF) 11. 05. 2015. г. Приступљено 13. 02. 2009.
^ Lomont 2003, стр. 3.
^ McEniry 2007, стр. 2, 16.
^ Eberly, David (2002). „Fast Inverse Square Root” (PDF). Geometric Tools: 2—. Архивирано из оригинала (PDF) 24. 02. 2009. г. Приступљено 22. 03. 2009.
^ Ruskin, Elan (16. 10. 2009). „Timing square root”. Some Assembly Required. Архивирано из оригинала 25. 08. 2010. г. Приступљено 13. 09. 2010. Архивирано на сајту Wayback Machine (25. август 2010)

Литература

Kushner, David (2002). „The wizardry of Id”. IEEE Spectrum. 39 (8): 42—47. doi:10.1109/MSPEC.2002.1021943.
Blinn, Jim (2003). Jim Blinn's Corner: Notation, notation notation. Morgan Kaufmann. стр. 130. ISBN 978-1-55860-860-3.
Eberly, David (2001). 3D Game Engine Design. Morgan Kaufmann. стр. 504. ISBN 978-1-55860-593-0.

Спољашње везе

Кратка историја InvSqrt, Метју Робертсон
Брзи инверз квадратног корена, Крис Ломонт
Порекло брзог InvSqrt() игрице Quake3
Quake III Arena изворни код
Margolin, Tomer (27. 08. 2005). „Magical Square Root Implementation In Quake III”. CodeMaestro. The Coding Experience. Архивирано из оригинала 14. 04. 2012. г. Приступљено 10. 11. 2012. Архивирано на сајту Wayback Machine (14. април 2012)

[7] Коришћење типа long умањује портабилност овог кода на модерним системима. Како би се код извршавао исправно, sizeof(long) мора да буде 4 бајта, у супротном може да дође до негативних вредности у резултату. На многим модерним 64-битним системима, sizeof(long) је 8 бајтова.

[Beyond3D-1] а ^б ^в Sommefeldt, Rys (29. 11. 2006). „Origin of Quake3's Fast InvSqrt()”. Beyond3D. Приступљено 12. 02. 2009.

[FOOTNOTEBlinn2003130-2] Blinn 2003, стр. 130.

[IFIP-3] Middendorf, Lars; Mühlbauer, Felix; Umlauf, George; Bodba, Christophe (01. 6. 2007). „Embedded Vertex Shader in FPGA”. Ур.: Rettberg, Achin. Embedded System Design: Topics, Techniques and Trends. IFIP TC10 Working Conference:International Embedded Systems Symposium (IESS). et al. Irvine, California: Springer. стр. 155—164. ISBN 978-0-387-72257-3.

[FOOTNOTEEberly2001504-4] Eberly 2001, стр. 504.

[5] Lomont, Chris (2003). „Fast Inverse Square Root” (PDF). стр. 1. Приступљено 13. 02. 2009.

[6] McEniry, Charles (2007). „The Mathematics Behind the Fast Inverse Square Root Function Code” (PDF). стр. 1. Архивирано из оригинала (PDF) 11. 05. 2015. г. Приступљено 13. 02. 2009.

[FOOTNOTELomont20033-8] Lomont 2003, стр. 3.

[FOOTNOTEMcEniry20072,_16-9] McEniry 2007, стр. 2, 16.

[Eberly_2-10] Eberly, David (2002). „Fast Inverse Square Root” (PDF). Geometric Tools: 2—. Архивирано из оригинала (PDF) 24. 02. 2009. г. Приступљено 22. 03. 2009.

[11] Ruskin, Elan (16. 10. 2009). „Timing square root”. Some Assembly Required. Архивирано из оригинала 25. 08. 2010. г. Приступљено 13. 09. 2010. Архивирано на сајту Wayback Machine (25. август 2010)

[1]

[2]

[3]

[4]

[5]

[6]

[note 1]

[7]

[8]

[9]

[10]