Изворни код странице 0x5f3759df

__БЕЗКН__
[[Датотека:OpenArena-Rocket.jpg|мини|десно|300п|Израчунавања осветљења и рефлексија (овде приказани у [[пуцачка игра из првог лица|пуцачини из првог лица]] ''-{[[OpenArena]]}-'') користе брзи инверз квадратног корена за налажење [[упадни угао|упадног угла]].]]

'''Брзи инверз квадратног корена''' (познат и као '''-{Fast InvSqrt()}-''' или по [[хексадецимални систем|хексадекадној]] константи '''-{0x5f3759df}-''') је метод за рачунање x<sup>−½</sup>, [[мултипликативни инверз|мултипликативног инверза]] [[квадратни корен|квадратног корена]] броја записаног у 32-битној прецизности [[покретни зарез|покретног зареза]] у [[Једнострука тачност|IEEE 754]] формату. Алгоритам је вероватно развијен у компанији [[Силикон графикс]] почетком 1990-их, а његова имплементација се јавила 1999. у изворном коду игрице ''-{[[Quake III Arena]]}-'', али сам метод се није појавио на јавним форумима као што је -{[[Usenet]]}- све до 2002 или 2003.<ref name="Beyond3D">{{cite web|url=http://www.beyond3d.com/content/articles/8/|title=Origin of Quake3's Fast InvSqrt()|last=Sommefeldt|first=Rys|date=29. 11. 2006|work=Beyond3D|accessdate=12. 02. 2009.|archive-date=09. 02. 2009|archive-url=https://web.archive.org/web/20090209045625/http://www.beyond3d.com/content/articles/8/|url-status=}}</ref> У то време, првенствена предност алгоритма се састојала у избегавању рачунски скупих аритметичких операција у покретном зарезу, уместо којих се користе целобројне операције. Инверзни квадратни корен се користи у рачунању упадних углова и рефлексије светлости и сенки у [[рачунарска графика|рачунарској графици]].

Алгоритам узима 32-битни број у покретном зарезу као улаз, и складишти његову половину за каснију употребу. Затим се, посматрајући битове који представљају број у покретном зарезу као 32-битни цео број, спроводи операција логичког шифтовања удесно за један бит, а резултат те операције се одузима од „магичне“ константе -{[[хексадецимални систем|0x]]5f3759df}-. Ово је прва апроксимација инверзног квадратног корена улаза. Затим се битови поново посматрају као број у покретном зарезу и спроводи се једна итерација [[Њутнов метод|Њутновог метода]] како би се добила прецизнија апроксимација. Ово рачуна апроксимацију инверза квадратног корена броја у покретном зарезу отприлике четири пута брже него коришћењем дељења бројева у покретном зарезу.

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

== Мотивација ==
[[Датотека:Surface normal.png|мини|десно|Површинске нормале имају честу примену у израчунавањима осветљавања и сенки, што захтева израчунавање норми вектора. На слици је приказано поље вектора нормалних на површину.]]
Инверз квадратног корена броја у покретном зарезу се користи у рачунању [[вектор#Јединични вектор|нормализованог вектора]].{{sfn|Blinn|2003|pp=130}} Како програми који раде са [[3Д графика|3Д графиком]] користе ове нормализоване векторе за одређивање осветљења и [[Ламбертов косинусни закон|рефлексија]], неопходно је извршити милионе оваквих рачунања у секунди. Пре него што је развијен специјализовани хардвер који се бави трансформацијама и осветљењем, софтверско израчунавање је могло да буде врло споро. Конкретно, када је овај алгоритам развијен раних 1990-их, већина процесора је била много спорија у рачунању операција са покретним зарезом него у рачунању целобројних операција.<ref name="Beyond3D" />

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

:<math>\|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2}</math> је еуклидска норма вектора, аналогна [[еуклидска раздаљина|еуклидском растојању]] између две тачке у [[еуклидов простор|еуклидском простору]].

:<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\|</math> је нормализовани (јединични) вектор. Ако се са <math>\boldsymbol{x}</math> представи <math>v_1^2+v_2^2+v_3^2</math>, добије се

:<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{x}</math>, што повезује јединични вектор са инверзом квадратног корена компоненти раздаљине.

''-{Quake III Arena}-'' је користила алгоритам за брзи инверз квадратног корена како би убрзала израчунавање у [[графички процесор|графичкој процесној јединици]], али овај алгоритам је у међувремену имплементиран у специјалним хардверским [[вертекс шејдер]]има који користе -{[[FPGA]]}-.<ref name="IFIP">{{cite conference|last=Middendorf
| first =Lars
 |author2= Mühlbauer, Felix |author3= Umlauf, George |author4= Bodba, Christophe
 |date=01. 6. 2007.|title=Embedded Vertex Shader in FPGA
 | conference = [[International Federation for Information Processing|IFIP]] TC10 Working Conference:International Embedded Systems Symposium (IESS)
 | conferenceurl =
 | booktitle = Embedded System Design: Topics, Techniques and Trends
 | editor = Rettberg, Achin
 | others = et al.
 | volume =
 | edition =|publisher=Springer
 | location = [[Ервајн|Irvine, California]]|pages=155-164
|isbn = 978-0-387-72257-3
}}</ref>

== Преглед кода ==
Следи изворни код имплементације алгоритма за брзи инверз квадратног корена коришћен у игрици ''-{[[Quake III Arena]]}-'', са уклоњеним [[C препроцесор]]ским директивама, али са очуваним неизмењеним оригиналним коментарима:{{чињеница|date = 01. 2019.}}<!--mrtva veza do tog datuma.--><!--
YES, THE ORIGINAL SOURCE CODE INCLUDES "fuck" IN THE COMMENTS. THIS IS A DIRECT QUOTE. See [[WP:CENSOR]] before trying to remove it. -->
<source lang="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;
}
</source>

Како би се одредио инверз квадратног корена, полази се од апроксимације за <math>x^{-1/2}</math>, коју одређује софтвер, а затим се примењује нека нумеричка метода да би се апроксимација поправљала све док не дође у опсег прихватљивог одступања од тачног решења. [[Методи рачунања квадратног корена|Уобичајени софтверски методи]] са почетка 1990-их су прву апроксимацију извлачили из предефинисаних таблица.{{sfn|Eberly|2001|pp=504}} Горенаведени код се у пракси показао бржим од таблица, и отприлике четири пута бржи него кад би се користило уобичајено дељење у покретном зарезу.<ref>{{cite web|url=http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf|title=Fast Inverse Square Root |last=Lomont|first=Chris|date=2003|pages=1|accessdate=13. 02. 2009.}}</ref> Долазило је до извесног губитка у прецизности, али је он надомешћен значајним напретком у перформансама.<ref>{{cite web|url=http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf|title=The Mathematics Behind the Fast Inverse Square Root Function Code|last=McEniry|first=Charles|year=2007|pages=1|accessdate=13. 02. 2009.|archive-url=https://web.archive.org/web/20150511044204/http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf|archive-date=11. 05. 2015|url-status=dead}}</ref> Алгоритам је развијен за -{[[IEEE 754-1985]]}- 32-битне бројеве у покретном зарезу, али испитивање Криса Ломонта и касније Чарлса МакЕнирија је показало да би могао да буде имплементиран и у другим форматима бројева у покретном зарезу.

Предности у брзини које пружа овај алгоритам се између осталог заснивају на „досетки“ да се 32-битни број у покретном зарезу<!-- longword --><ref group=note>Коришћење типа <code>long</code> умањује портабилност овог кода на модерним системима. Како би се код извршавао исправно, <code>sizeof(long)</code> мора да буде 4 бајта, у супротном може да дође до негативних вредности у резултату. На многим модерним 64-битним системима, <code>sizeof(long)</code> је 8 бајтова.</ref> третира као цео број и одузме од специфичне константе, '''-{0x5f3759df}-'''. Сврха константе није одмах јасна некоме ко прегледа код, па се стога, као и друге сличне константе које се користе у програмирању, често назива „[[Магични број (програмирање)|магичним бројем]]“.<ref name="Beyond3D" />{{sfn|Lomont|2003|pp=3}}{{sfn|McEniry|2007|pp=2, 16}}<ref name="Eberly 2">{{Cite document|last=Eberly| first = David| title = Fast Inverse Square Root| publisher = Geometric Tools|year=2002| url = http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf|pages=2-| accessdate=22. 03. 2009.| postscript = <!--None-->| journal = | archive-url = https://web.archive.org/web/20090224214314/http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf| archive-date=24. 02. 2009|url-status=dead| df = }}</ref> Ово целобројно одузимање и битовско шифтовање даје 32-битну вредност која се затим поново посматра као број у покретном зарезу, и представља грубу апроксимацију инверза квадратног корена почетног броја. Примењује се једна итерација Њутновог метода како би се добило на прецизности, и ту се код завршава. Алгоритам генерише разумно прецизне резултате користећи јединствену прву апроксимацију за [[Њутнов метод]]. Међутим, ово је знатно спорије и мање прецизно него коришћење -{SSE}- инструкције <code>rsqrtss</code> на x86 процесорима, која је такође објављена 1999.<ref>{{cite web |url=http://assemblyrequired.crashworks.org/2009/10/16/timing-square-root/ |title=Timing square root |work=Some Assembly Required |first=Elan |last=Ruskin |date=16. 10. 2009. |accessdate=13. 09. 2010. |archive-url=https://web.archive.org/web/20100825093355/http://assemblyrequired.crashworks.org/2009/10/16/timing-square-root/ |archive-date=25. 08. 2010 |url-status=dead }} {{Wayback|url=http://assemblyrequired.crashworks.org/2009/10/16/timing-square-root/ |date=20100825093355 }}</ref>

== Напомене ==
<references group=note/>

== Референце ==
{{reflist}}

== Литература ==
* {{cite journal|last=Kushner|first=David|date=2002|title=The wizardry of Id|journal=IEEE Spectrum|volume=39|issue=8|url=|doi=10.1109/MSPEC.2002.1021943|pages=42-47}}
* {{Cite book|ref=harv|last=Blinn|first=Jim|title=Jim Blinn's Corner: Notation, notation notation|url=https://archive.org/details/jimblinnscornern0000blin|publisher=Morgan Kaufmann|year=2003|pages=[https://archive.org/details/jimblinnscornern0000blin/page/130 130]|isbn=978-1-55860-860-3}}
* {{Cite book|ref=harv|last=Eberly|first=David|title=3D Game Engine Design|url=https://archive.org/details/isbn_9781558605930|publisher=Morgan Kaufmann|year=2001|pages=[https://archive.org/details/isbn_9781558605930/page/504 504]|isbn=978-1-55860-593-0}}

== Спољашње везе ==
* [https://web.archive.org/web/20130309065349/http://eggroll.unbsj.ca/rsqrt/rsqrt.pdf Кратка историја -{InvSqrt}-], Метју Робертсон
* [http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf Брзи инверз квадратног корена], Крис Ломонт
* [http://www.beyond3d.com/content/articles/8/ Порекло брзог InvSqrt() игрице -{Quake3}-] {{Wayback|url=http://www.beyond3d.com/content/articles/8/ |date=20090209045625 }}
* [http://www.idsoftware.com/business/techdownloads/ -{Quake III Arena}- изворни код]
* {{cite web|url=http://www.codemaestro.com/reviews/9|title=Magical Square Root Implementation In Quake III|last=Margolin|first=Tomer|date=27. 08. 2005.|work=CodeMaestro|publisher=The Coding Experience|accessdate=10. 11. 2012|archive-url=https://web.archive.org/web/20120414130404/http://www.codemaestro.com/reviews/9|archive-date=14. 04. 2012|url-status=dead}} {{Wayback|url=http://www.codemaestro.com/reviews/9 |date=20120414130404 }}

{{нормативна контрола}}

[[Категорија:Алгоритми]]