Швидкий інверсний квадратний корінь, Математика, FANDOM powered by Wikia
Швидкий зворотний квадратний корінь(такожшвидкий InvSqrt()або0x5f3759dfза використовуваною «магічною» константою) — цілочисловий алгоритм обчислення зворотного квадратного кореня $ y=\frac> $ для 32-бітних чисел з плаваючою комою.
Алгоритм
Алгоритм приймає 32-бітове число з плаваючою комою (одинарної точності) як вихідні дані, і здійснює над ним наступні операції:
- обчислює половину значення числа та зберігає для подальшого використання
- трактуючи 32-бітне з плаваючою комою як 32-бітне ціле:
- здійснює логічне зрушення вправо на один біт
- віднімає число з «магічної» константи 5f3759df16
Алгоритм дозволяє обчислювати приблизне значення зворотного квадратного кореня в середньому у 4 рази швидше, ніж з використанням FPU.
Історія Правити
Алгоритм був, ймовірно, розроблений у Silicon Graphics у 1990-х, а реалізація з'явилася в 1999 році у вихідному коді комп'ютерної гри Quake III Arena, але цей метод не з'являвся на загальнодоступних форумах, таких як Usenet, до 2002-2003 років. Алгоритм генерує досить точні результати, використовуючи унікальне наближення першого методу Ньютона. У той час основною перевагою алгоритму була відмова від дорогих обчислювальних операцій з плаваючою комою на користь цілих операцій. Зворотні квадратні корені використовуються для розрахунку кутів падіння та відображення для освітлення тазатінення у комп'ютерній графіці.
Алгоритм спочатку приписувався Джону Кармаку, але вивчення питання показало, що код мав глибше коріння як в апаратній, так і в програмній сферах комп'ютерної графіки. Виправлення та зміни проводилися як Silicon Graphics так і 3dfx Interactive, при цьому як раннє використання відома реалізація Гері Тароллі для SGI Indigo. Невідомо, як виводилася ця константа від початку, проте розслідування проливає світло на можливі методи.
З виходом у 1998 році набору інструкцій 3DNow! у процесорах фірми AMD з'явилася інструкція асемблера PFRSQRT для швидкого наближеного обчислення інверсного квадратного кореня.
Мотивування Правити
Поверхня нормалей широко використовуються у розрахунках освітлення та затінення, що вимагають розрахунку норм для векторів. Тут показано поле векторів нормалі до поверхні
Інверсне квадратне коріння числа з плаваючою комою використовується для обчислення нормалізованого вектора. Оскільки програма з 3D графікою використовує ці нормалізовані вектори визначення освітлення і відображення, мільйони цих обчислень повинні виконуватися за секунду. Перш ніж було створено спеціальне апаратне забезпечення для обробки трансформацій та освітлення, програмне забезпечення обчислень могло бути повільним. Зокрема, на початку 1990-х, коли код було розроблено, більшість обчислень з плаваючою комою відставали за продуктивністю від операцій із цілими числами.
Щоб нормалізувати вектор, його довжина визначається шляхом обчислення норми: квадратний корінь суми квадратів компонент вектора. Коли кожен компонент вектора ділиться з його довжину, новий вектор, званий одиничним, спрямований у тому напрямі.
$ \\boldsymbol\ =\sqrt^2+^2+^2> $ - це евклідова норма вектора, аналог Евклідової дистанції між двома точками у просторі. $ \boldsymbol> = Boldsymbol / Boldsymbol $ - це нормалізований одиничний вектор. Обчислене $ ^2+^2+^2 $ позначимо як $ \boldsymbol $ , $ \boldsymbol> = \boldsymbol / \sqrt $ визначає співвідношення одиничного вектора і зворотного квадратного кореня від $ x $.
Quake III Arena використовує алгоритм швидкого зворотного квадратного кореня для прискорення обробки графіки обчислювальними блоками, але з того часу алгоритм вже було реалізовано деяких спеціалізованих апаратних вершинних шейдерах, використовуючи спеціальні програмовані матриці (FPGA).