Быстрый обратный квадратный корень

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Вычисление освещения и отражения (показано на примере шутера от первого лица OpenArena) использует в коде быстрый инверсный квадратный корень для вычисления углов падения и отражения.

Бы́стрый обра́тный квадра́тный ко́рень (также быстрый InvSqrt() или 0x5f3759df по используемой «магической» константе) — это целочисленный алгоритм вычисления обратного квадратного корня y=\frac{1}{\sqrt{x}} для 32-битных чисел с плавающей запятой.

Алгоритм[править | править вики-текст]

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

  • вычисляет половину значения числа и сохраняет для дальнейшего использования
  • трактуя 32-битное с плавающей запятой как 32-битное целое:
  • (в трактовке результата как 32-битного с плавающей запятой на этом этапе получается первое приближение обратного квадратного корня исходного числа)
  • вычисляет одну итерацию метода Ньютона для получения более точного приближения

Алгоритм позволяет вычислять приблизительное значение обратного квадратного корня в среднем в 4 раза быстрее, чем с использованием FPU.

История[править | править вики-текст]

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

Алгоритм изначально приписывался Джону Кармаку, но изучение вопроса показало, что код имел более глубокие корни как в аппаратной, так и в программной сферах компьютерной графики. Исправления и изменения производились как Silicon Graphics так и 3dfx Interactive, при этом как самое раннее использование известна реализация Гэри Таролли для SGI Indigo. Константа, которая используется для приближенного вычисления быстрого обратного квадратного корня, изначально является табличным значением Числа одинарной точности для вычисления первой итерации значения квадратного корня. Данная константа равна значению квадратного корня из половины максимально возможного хранимого значения числа в данном формате.

Так как значение {2}^{128} = nan

FloatToHex({2}^{128}*0,5)=7F000000

13043817825332782212 = \sqrt{170141183460469231731687303715884105728}

13043817825332782212 в виде константы с плавающей точкой в шестнадцатеричной системе счисления выглядит как 0x5f3504f3. И при использовании ее в алгоритме вычисления обратного квадратного корня также как и 5f3759df дает приближенное значение. Константа 5f3759df получена следующим образом:

FloatToHex(\sqrt{{2}^{128}*0,512964})=5F3759DF

С выходом в свет в 1998 году набора инструкций 3DNow! в процессорах фирмы AMD появилась ассемблерная инструкция PFRSQRT для быстрого приближенного вычисления инверсного квадратного корня. Также можно получить константу для Чисел двойной точности, но это не будет иметь практического применения так как точность вычислений не увеличится, поэтому инструкции для вычисления быстрого обратного квадратного корня для Чисел двойной точности не была добавлена.

Мотивировка[править | править вики-текст]

Поверхность нормалей широко используются в расчетах освещения и затенения, требующих расчета норм для векторов. Здесь показано поле векторов нормали к поверхности.

Инверсный квадратный корень числа с плавающей запятой используется для вычисления нормализованного вектора. Так как программа с 3D графикой использует эти нормализованные векторы для определения освещения и отражения, за секунду должны вычисляться миллионы этих корней. До того как было создано специальное аппаратное обеспечение для обработки трансформаций и освещения, программное обеспечение вычислений могло быть медленным. В частности, в начале 1990-х, когда код был разработан, большинство вычислений с плавающей запятой отставало по производительности от операций с целыми числами.

Чтобы нормализовать вектор, надо сначала определить его длину путем вычисления его нормы: квадратный корень суммы квадратов компонент вектора, а затем каждый компонент вектора разделить на полученную длину. Получается новый вектор, называемый единичным, и направленный в том же направлении, что и исходный.

\|\boldsymbol{v}\| = \sqrt{{v_1}^2+{v_2}^2+{v_3}^2} — это евклидова норма вектора, аналог Евклидовой дистанции между двумя точками в пространстве.
\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\| — это нормализованный единичный вектор. Вычисленное {v_1}^2+{v_2}^2+{v_3}^2 обозначим как \boldsymbol{x},
\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{x}, определяет соотношение единичного вектора и обратного квадратного корня от x.

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

Ссылки[править | править вики-текст]