Бърз обратен квадратен корен

обратен

Бърз обратен квадратен корен(същоFast InvSqrt()или0x5F3759DFчрез използваната "магическа" константа) е бърз приблизителен алгоритъм за изчисляване на обратен квадратен корен y = 1 x >>> за положителни 32-битови числа с плаваща запетая. Алгоритъмът използва целочислени операции "изваждане" и "битово изместване", както и дробни "изваждане" и "умножение" - без бавни операции "деление" и "квадратен корен". Въпреки "хакването" на битово ниво, приближението е непрекъснато: близките аргументи дават близък резултат. Точността (по-малко от 0,2% надолу и никога нагоре) не е достатъчна за реални числени изчисления, но е напълно достатъчна за триизмерна графика.

Съдържание

Алгоритъмът приема 32-битово число с плаваща запетая (единична точност) като вход и извършва следните операции върху него:

  • изчислява половината от стойността на число и го съхранява за по-късна употреба
  • третиране на 32-битова плаваща запетая като 32-битово цяло число:
  • извършва изместване надясно с един бит
  • изважда число от "магическата" константа 5F3759DF16
  • (третирането на резултата като 32-битова плаваща запетая на този етап дава първото приближение на обратния корен квадратен от оригиналното число)
  • изчислява една итерация на метода на Нютон, за да получи по-точно приближение.

    • Структурата на 4-байтова фракция е:

    ЗнакМантисов ред0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 = ( 1 + 2 − 2 ) ⋅ 2 − 3 = 0,156 25 )\cdot 2^=015625>
    3124231615870

    Имаме работа само с положителни числа (знаковият бит е нула), не денормализирани, не ∞ и не NaN. Такива числа се записват в стандартна форма като 1.xxxx2·2 k [1] и главното устройство не се съхранява (имплицитно устройство). В допълнение, машинните дробни числаимат предубеден ред: 2 0 се записва като 011.1111.12.

    Нека се опитаме да изведемkпрезaиb:k=a− ​​​​011.1111.12 = 111.1110.02 − 2b. Следователноb= (1011.1101.12 − a)/2 (за четноk).

    Сега нека видим какво се случва, акоkе нечетно. В такава ситуацияbе с едно по-голямо и двата случая могат да се комбинират във формулата:b= [(1011.1110.02 −a)/2] .

    Ако добавим битове от мантисата (обозначени със звездички) отдясно, тогава конструкциитеb*** = [(1011.1110.0***0 − a***)/2] иb*** = (101.1111.00*** − [a***/2]) се различават с един най-млад значим бит от мантисата. Което дава: горният байт е 5F, вторият в диапазона 00 ... 3F. Останалите битове на мантисата са избрани така, че да минимизират грешката.

    Не е известно откъде идва константата 0x5F3759DF ≈ 1.432430 2 63. Чрез груба сила Крис Ломонт и Матю Робъртсън установиха, че най-добрата константа за float е 0x5F375A86 ≈ 1.432450 2 63 , за double е 0x5FE6EB50C7B537A9. Вярно, че за double алгоритъмът е безсмислен (не дава печалба в точността в сравнение с float). По-фините изчисления, като се вземе предвид методът на Нютон, дават резултат, който съвпада с емпиричната константа на Ломонт [3] .

    Има подобни алгоритми за други степени, като квадратен или кубичен корен [4] .

    Алгоритъмът вероятно е разработен в Silicon Graphics през 1990 г., а през 1999 г. се появява реализация в изходния код на компютърната игра Quake III Arena, но методът не се появява напублични форуми като Usenet до 2002-2003 г. Алгоритъмът генерира сравнително точни резултати, използвайки уникалното първо приближение на метода на Нютон. По това време основното предимство на алгоритъма беше отхвърлянето на скъпи изчисления с плаваща запетая в полза на операции с цели числа. Обратните квадратни корени се използват за изчисляване на ъгли на падане и отражение за осветление и засенчване в компютърната графика.

    Първоначално алгоритъмът беше приписан на Джон Кармак, но той призна, че Майкъл Абраш го е донесъл на id Software. Проучването на проблема показа, че кодът има по-дълбоки корени както в хардуерната, така и в софтуерната област на компютърната графика. Поправки и промени бяха направени както от Silicon Graphics, така и от 3dfx Interactive, като реализацията на Gary Tarolli за SGI Indigo е известна като най-ранната употреба.

    С пускането на 3DNow! В процесорите на AMD се появи инструкция за асемблер PFRSQRT за бързо приблизително изчисляване на обратния квадратен корен. Възможно е също така да се получи константа за двойни числа, но това е безсмислено, тъй като прецизността на изчисленията няма да се увеличи, така че не са добавени инструкции за изчисляване на бърз обратен корен квадратен за двойни.

    Обратният корен квадратен от число с плаваща запетая се използва за изчисляване на нормализирания вектор. Тъй като програмата за 3D графики използва тези нормализирани вектори за определяне на осветлението и отражението, милиони от тези корени трябва да се изчисляват в секунда. Преди да има специален хардуер за обработка на трансформации и осветление, изчислителният софтуер можеше да бъде бавен. По-специално, в началото на 90-те години, когато кодът е разработен, повечетоизчисленията с плаваща запетая изоставаха в производителността спрямо операциите с цели числа.

    За да нормализирате вектор, първо трябва да определите дължината му, като изчислите неговата норма: корен квадратен от сумата на квадратите на компонентите на вектора и след това да разделите всеки компонент на вектора на получената дължина. Получава се нов вектор, наречен единичен вектор и насочен в същата посока като оригиналния.

    Quake III Arenaизползва бърз алгоритъм за обратен квадратен корен, за да ускори графичната обработка от изчислителните единици, но алгоритъмът оттогава е внедрен в някои специализирани хардуерни вертекс шейдъри, използващи специални програмируеми масиви (FPGA).