Kokia viena kodo eilutė sukrėtė programavimo pasaulį?

  i = 0x5f3759df - ( i >> 1 ); // what the fuck?

Ši eilutė pasirodė „id Software“ kompanijos „Quake 3 Arena“ (1999) pradiniame kode ir yra funkcijos šio žaidimo grafinėje komponentėje dalimi. Ji skirta slankaus kablelio kintamojo atvirkštinės šaknies (1/sqrt(x)) apytiksliam paskaičiavimui. Ši funkcija ypač svarbi, nes ji naudojama atstumui tarp vektorių paskaičiavimui. Žaidimuose Quake scene jos prireikia milijonus kartų per sekundę – tad sparta ypač svarbi. Anksčiau tam skirtos funkcijos pirmiausia apskaičiuodavo rezultato įvertį naudodamos paieška lentelėje (lookup), o tada jį patikslindavo panaudodamos Niutono aproksimacijos algoritmą. Naujoji funkcija, pavadinta greitąja atvirkštine kvadratine šaknimi, pasinaudojo IEEE 754 slankiojo kablelio formatu, kad pirmąjį įvertį apskaičiuotų daug greičiau ir sunaudodama daug mažiau atminties nei naudojant lentelę. Tai buvo daroma paimant 32 bitų slankiojo kablelio bitus kaip sveikąjį skaičių, pastumiant tą skaičių per vieną bitą į dešinę, o tada atimant rezultatą iš magiškosios konstantos. Tada gauti bitai vėl traktuojami kaip slankiojo kablelio skaičiaus ir tik tada patikslinami minėtu aproksimacijos metodu.

O „magiškas skaičius“ atsirado dėl slankaus skaičiaus su laipsniu (tokio, kaip 5.6*109) saugojimo IEEE 754 formatu ypatybių, kai laipsnis (eksponentė) buvo saugomas atskiruose bituose (dabar nesigilinsime į subtilybes).
Ir įdomiausia, kad ši nepaprastai greitas sprendimas žemos rezoliucijos grafikai bent 5 m. tyliai sau kiurksojo „Quake“ kode, nors jo ištakos atrandamos daugiau nei prieš dešimtmetį. Jei tai būtų atlikta akademiniuose sluoksniuose, vien šios eilutės būtų pakakę disertacijai.

O jos istorija tokia.
Kanadietis William Kahan’as1) ir K.C. Ng’as iš Kalifornijos un-to Berklyje 1986 m. parašė straipsnį (likusį nepublikuotu) apie kvadratinės šaknies reikšmės paskaičiavimą panaudojant manipuliavimus bitais ir panaudojant Niutono aproksimaciją. Po poros metų apie tą techniką sužinojo Cleve Moler’is2) iš „Ardent Computer“ ir ja pasidalijo su bendradarbiu Greg Walsh’u3), kuris ir išvystė tą garsųjį atvirkštinės kvadratinės reikšmės paskaičiavimo algoritmą. Gary Tarolli4) tuo metu konsultavo „Kubota“ finansuojančią „Ardent Computer“, ir tikriausiai jis apie 1994 m. algoritmą „atnešė“ į „3dfx Interactive“. Jim Blinn’as5) jį pristatė „IEEE Computer Graphics and Applications“ 1997 m. liepos-rugpjūčio numeryje. Kodo analizė išsiaiškino, kad algoritmo variantas buvo naudojamas ir „Activision“ kompanijos žaidime „Interstate'76“. Į „id Software“ algoritmą greičiausiai atnešė Brian Hook’as. Kodas plačiai pasklido 2002-2003 m. Buvo ginčijamasi, kas parašė algoritmą ir kaip išvesta magiškoji konstantą – tol, kol 2006 m. klausimą išsprendė pats algoritmo autorius Greg Walsh’as. 2007 m. algoritmas panaudotas kai kurių aparatinių plokščių šešėliavimuose.

Ištobulėjus aparatinei įrangai, ypač x86 procesorių SSE instrukcijai rsqrtss (įtrauktai 1999-ais ir spartesnei daugiau nei 5 kartus). šis algoritmas jau nebėra geriausias pasirinkimas, tačiau išlieka įdomiu istoriniu momentu.

1) Viljamas Kechanas (William "Velvel" Morton Kahan, g. 1933 m.) - žydų kilmės kanadiečių matematikas ir kompiuterininkas, Kalifornijos un-to Berklyje profesorius. Gavo Tiuringo premiją (1989) už indėlį į skaitmeninę analizę. Sukūrė (pavadintą jo vardu) skaičių IEEE 754 pavaizdavimu sudėties algoritmą minimizuojant klaidą. 9-me dešimtm. sukūrė programą paranoia, tikrinančią platų ratą galimų klaidų operacijose su slankiais skaičiais. Rengia naują slankaus skaičiaus pavaizdavimo standartą (IEEE 754-2008).

2) Klivas Mouleris (Cleve Barry Moler, g. 1939 m.) - amerikiečių matematikas ir programuotojas, specializuojantis skaitmeninėje analizėje. 8-ojo dešimtm. antroje pusėje sukūrė FORTRAN bibliotekas LINPACK ir EISPACK. Taip pat sukūrė MATLAB paketą ir 1984 m. jo komercializavimui kartu su Jack Little įsteigė „MathWorks“. Iki 1989 m. dar dirbo ir „Intel Hypercube“, kur įvedė terminą „nepatogiai lygiagretus“ (embarrassingly parallel). Parašė 4 vadovėlius apie skaitmeninę analizę.

3) Gregas Velšas (Greg Walsh) - amerikiečių kompiuterininkas, pradėjęs dirbti su Internetu ir paskirstytais skaičiavimais, kad dar net nebuvo Interneto ir padėjęs kurti pirmąjį WYSIWYG redaktorių Xerox PARC. Vėliau padėjo įsteigti „Ardent Computer“ kompaniją. Jos „Titan“ grafinis kompiuteris turėjo problemų su greitaveika ir G. Velšas sukūrė greitą 1/sqrt(x) funkciją, kad programinė įranga galėtų sparčiai veikti kompiuteriuose, tam neturinčiuose aparatinio palaikymo. Tam idėją gavo iš K. Moulerio, tuo metu dirbusio „Ardent“. K. Mouleris tuo metu nagrinėjo N-R iteraciją aproksimacijai, tad G. Velšas taip pat, naudodamas panašius (tik sudėtingesnius) metodus, parašė ir 1/cuberoot(x).

4) Garis Tarolis (Gary Tarolli) - amerikiečių kompiuterininkas, išradėjas, 1994 m. įsteigęs „3Dfx Interactive“ ir joje dirbęs iki 2000-ųjų. Vėliau iki 2016 m. dirbo „NVidia“ kaip 3D architektas, kūręs GPU. Turi kelis patentus.

5) Džeimsas Blinas (James F. Blinn, g. 1949 m.) - amerikiečių kompiuterininkas, išgarsėjęs kaip grafikos ekspertas NASA JPL laboratorijoje (iki 1995 m.), ypač animacijose „Voyager“ projekte, K. Sagano dokumentiniame cikle „Kosmosas“ (1980) ir Blinn–Phong’o šešėliavimo modelio tyrinėjimais. Po NASA prisijungė prie „Microsoft Research“, į pensiją išėjęs 2009 m. 1987-2007 m. vedė „Džimo Blino kampelis“ rubriką „IEEE Computer Graphics & Applications“. Jam priskiriamas Jam Blino dėsnis, teigiantis, kad atvaizdavimo laikas išlieka pastovus, net ir spartėjant kompiuteriams – animatoriai linkę gerinti kokybę, vaizduoti sudėtingesnes scenas sudėtingesniais algoritmais...

Papildomai skaitykite:
Kaip suliesėti?
Vykdyti ir laukti
Unix komandinės eilutė
Mašininės grafikos pradžia
C/C++: Ką reiškia "static"?
Programuotojus į savartyną!
Pirmasis „Java“ įskiepis Lietuvoje
C++: mutable - nauja kalbos savybė
Intuityvus Hafmano kodo paaiškinimas
Sunkus „Linux“ posūkis nuo C link „Rust“
S. Krėjus: kūręs galingiausius kompiuterius!
Suleidote arklius – užverkite ir tvarto duris!
Rašybos tikrinimo programa RAŠTAS
Įvadas į Perl kalbą: Kas naudoja Perl?
Lambda išraiškos – Java į naują lygį
Džonas Bakas – FORTRAN tėvas
Į Mėnulį skridę kompiuteriai
Tcl kalba - iš „susierzinimo“
Skriptai - ateities kalbos?
Kobolo motina
Vartiklis