Бърз обратен квадратен корен, математика, FANDOM, захранван от Wikia
Бърз обратен квадратен корен(същобърз InvSqrt()или0x5f3759dfизползвайки използваната "магическа" константа) - целочислен алгоритъм за изчисляване на обратен квадратен корен $ y=\frac> $ за 32-битови числа с плаваща запетая.
Редактиране на алгоритъм
Алгоритъмът приема 32-битово число с плаваща запетая (единична точност) като вход и извършва следните операции върху него:
- изчислява половината от стойността на число и го съхранява за по-късна употреба
- третиране на 32-битова плаваща запетая като 32-битово цяло число:
- извършва логическо изместване надясно с един бит
- изважда число от "магическата" константа 5f3759df16
Алгоритъмът ви позволява да изчислите приблизителната стойност на обратния квадратен корен средно 4 пъти по-бързо от използването на FPU.
Редактиране на историята
Алгоритъмът вероятно е разработен в Silicon Graphics през 90-те години на миналия век, а реализация се появява през 1999 г. в изходния код на компютърната игра Quake III Arena, но методът не се появява на публични форуми като Usenet до 2002-2003 г. Алгоритъмът генерира сравнително точни резултати, използвайки уникалното първо приближение на метода на Нютон. По това време основното предимство на алгоритъма беше отхвърлянето на скъпи изчисления с плаваща запетая в полза на операции с цели числа. Обратните квадратни корени се използват за изчисляване на ъглите на падане и отражение за осветяване изасенчване в компютърната графика.
Първоначално алгоритъмът беше приписан на Джон Кармак, но изследването на проблема показа, че кодът има по-дълбоки корени както в хардуерните, така и в софтуерните области на компютърната графика. Поправки и промени са направени както от Silicon Graphics, така и от 3dfx Interactive, като реализацията на Gary Tarolli за SGI Indigo е известна като най-ранната употреба. Не е известно как първоначално е получена тази константа, но разследването хвърля светлина върху възможните методи.
С пускането на 3DNow! В процесорите на AMD се появи инструкция за асемблер PFRSQRT за бързо приблизително изчисляване на обратния квадратен корен.
Редактиране на мотивацията
Повърхностните нормали се използват широко при изчисления на осветление и засенчване, които изискват изчисляване на норми за вектори. Тук е показано полето от нормални вектори към повърхността
Обратният корен квадратен от число с плаваща запетая се използва за изчисляване на нормализирания вектор. Тъй като програмата за 3D графики използва тези нормализирани вектори, за да определи осветлението и отражението, милиони от тези изчисления трябва да се извършват в секунда. Преди да има специален хардуер за обработка на трансформации и осветление, изчислителният софтуер можеше да бъде бавен. По-специално, в началото на 90-те години, когато кодът беше разработен, повечето изчисления с плаваща запетая изоставаха по отношение на производителността на целочислените операции.
За да се нормализира вектор, неговата дължина се определя чрез изчисляване на неговата норма: корен квадратен от сумата от квадратите на компонентите на вектора. Когато всеки компонент на вектор се раздели на неговата дължина, новият вектор, наречен единичен вектор, сочи в същата посока.
$ \\boldsymbol\ =\sqrt^2+^2+^2> $ е евклидовата норма на вектор, аналогична на евклидовото разстояние между две точки в пространството. $\boldsymbol> = \boldsymbol / \\boldsymbol\ $ е нормализираният единичен вектор. Изчислените $ ^2+^2+^2 $ ще бъдат обозначени като $ \boldsymbol $ , $ \boldsymbol> = \boldsymbol / \sqrt $, определя съотношението на единичния вектор и обратния квадратен корен на $ x $.
Quake III Arena използва бърз алгоритъм за обратен квадратен корен, за да ускори обработката на графики от изчислителни единици, но алгоритъмът оттогава е внедрен в някои специализирани хардуерни вертексни шейдъри, използващи специални програмируеми масиви (FPGA).