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

Расчеты освещения и отражения (показанные здесь в шутере от первого лица OpenArena ) используют быстрый код обратного квадратного корня для вычисления углов падения и отражения.

Быстрое обратное квадратного корня , иногда называют Fast InvSqrt () или с помощью шестнадцатеричной константы 0x5F3759DF , представляет собой алгоритм , который оценивает $1$ $/$ $\sqrt$ $х$ , в возвратно - поступательное (или мультипликативный обратный) от квадратного корня из 32-битной плавающей точкой число $x$ в формате с плавающей запятой IEEE 754 . Эта операция используется в цифровой обработке сигналов для нормализации вектора, т. Е. Масштабирования его до длины 1. Например, программы компьютерной графики используют обратные квадратные корни для вычисления углы падения и отражения для освещения и затемнения . Алгоритм наиболее известен своей реализацией в 1999 году в исходном коде Quake III Arena , видеоигры -шутера от первого лица, в которой интенсивно использовалась трехмерная графика . Алгоритм только начал появляться на публичных форумах, таких как Usenet, в 2002 или 2003 годах. ^[1]^{[примечание 1]} В то время вычисление обратной величины числа с плавающей запятой , как правило, было дорогостоящим с точки зрения вычислений, особенно в больших масштабах; быстрый обратный квадратный корень обошел этот шаг.

Алгоритм принимает на вход 32-битное число с плавающей запятой и сохраняет уменьшенное вдвое значение для дальнейшего использования. Затем, рассматривая биты, представляющие число с плавающей запятой, как 32-битное целое, выполняется логический сдвиг вправо на один бит, и результат вычитается из числа 0x 5F3759DF, которое является представлением с плавающей запятой аппроксимации √ 2 ¹²⁷ . ^[3] Это приводит к первому приближению обратного квадратного корня из входных данных. Снова обрабатывая биты как число с плавающей запятой, он выполняет одну итерацию метода Ньютона , что дает более точное приближение.

Первоначально алгоритм был приписан Джону Кармаку , но расследование показало, что код имеет более глубокие корни как в аппаратной, так и в программной части компьютерной графики. Корректировки и изменения прошли как через Silicon Graphics, так и через 3dfx Interactive , причем реализация Гэри Таролли для SGI Indigo была самым ранним из известных способов использования. Неизвестно, как изначально была получена константа, хотя исследование пролило свет на возможные методы. ^{[ необходима цитата ]}

С последующим усовершенствованием аппаратного обеспечения, особенно с инструкцией x86 SSErsqrtss , этот метод, как правило, неприменим к современным вычислениям ^[4], хотя он остается интересным примером как исторически ^{[5], так} и для более ограниченных машин, таких как недорогие встроенные системы. Однако все больше производителей встраиваемых систем включают тригонометрические и другие математические ускорители, такие как CORDIC , что устраняет необходимость в таких алгоритмах.

Мотивация [ править ]

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

Двумерный пример использования нормали

C

для определения угла отражения от угла падения; в данном случае при отражении света от изогнутого зеркала. Быстрый обратный квадратный корень используется для обобщения этого вычисления на трехмерное пространство.

Обратный квадратный корень из числа с плавающей запятой используется при вычислении нормализованного вектора . ^[6] Программы могут использовать нормализованные векторы для определения углов падения и отражения . Программы трехмерной графики должны выполнять миллионы этих вычислений каждую секунду для имитации освещения. Когда код был разработан в начале 1990-х годов, большая часть вычислительной мощности с плавающей запятой отставала от скорости обработки целых чисел. ^[1] Это было проблемой для программ 3D-графики до появления специализированного оборудования для обработки преобразований и освещения .

Длина вектора определяется вычислением его евклидовой нормы : квадратного корня из суммы квадратов компонентов вектора . Когда каждый компонент вектора делится на эту длину, новый вектор будет единичным вектором, указывающим в том же направлении. В графической программе 3D, все векторы в трехмерном мерном пространстве, так что $V$ будет вектором $(v 1, v 2, v 3)$ .

{\ displaystyle \ | {\ boldsymbol {v}} \ | = {\ sqrt {v_ {1} ^ {2} + v_ {2} ^ {2} + v_ {3} ^ {2}}}}

- евклидова норма вектора.

{\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ frac {\ boldsymbol {v}} {\ left \ | {\ boldsymbol {v}} \ right \ |}}}

- нормализованный (единичный) вектор, используя $|| v || 2,$ чтобы представить $v 21 + v 22 + v 23$ .

{\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ frac {\ boldsymbol {v}} {\ sqrt {\ left \ | {\ boldsymbol {v}} \ right \ | ^ {2}}} }}

который связывает единичный вектор с обратным квадратным корнем из компонентов расстояния. Обратный квадратный корень можно использовать для вычисления $v̂,$ потому что это уравнение эквивалентно

{\ displaystyle {\ boldsymbol {\ hat {v}}} = {\ boldsymbol {v}} \, {\ frac {1} {\ sqrt {\ left \ | {\ boldsymbol {v}} \ right \ | ^ {2}}}}}

где дробный член является корнем, обратным квадратным из $|| v || 2$ .

В то время деление с плавающей запятой было обычно дорого по сравнению с умножением; Быстрый алгоритм вычисления обратного квадратного корня обходит этап деления, что дает ему преимущество в производительности. Quake III Arena , шутер от первого лица , использовала быстрый алгоритм обратного извлечения квадратного корня для ускорения графических вычислений, но с тех пор этот алгоритм был реализован в некоторых специализированных аппаратных вершинных шейдерах с использованием программируемых вентильных матриц (FPGA). ^[7]

Обзор кода [ править ]

Следующий код представляет собой быструю реализацию метода обратного квадратного корня из Quake III Arena , лишенную директив препроцессора C , но содержащую точный исходный текст комментария: ^[8]

float  Q_rsqrt (  число с плавающей запятой  ) { long i ; float x2 , y ; const float threehalfs = 1,5F ;        x2  =  число  *  0,5F ; y  =  число ; я  =  *  (  длинный  *  )  & y ;  // злой взлом уровня битов с плавающей запятой i  =  0x5f3759df  -  (  i  >>  1  );  // что за хрень? у  =  *  (с  плавающей запятой  *  )  & я ; y  =  y  *  (  три половины  -  (  x2  *  y  *  y )  );  // 1-я итерация // y = y * (threehalfs - (x2 * y * y)); // 2-я итерация, это можно удалитьвернуть  y ; }

В то время, общий метод для вычисления обратного квадратного корня был вычислить приближение для $1$ $/$ $\sqrt$ $х$ , то пересмотреть , что аппроксимация с помощью другого метода , пока не пришло в пределах приемлемого диапазона ошибок фактического результата. Обычные программные методы в начале 1990-х годов основывались на приближенных значениях таблицы поиска . ^[9] Ключом к быстрому вычислению обратного квадратного корня было прямое вычисление приближения с использованием структуры чисел с плавающей запятой, что оказалось быстрее, чем поиск в таблице. Алгоритм был примерно в четыре раза быстрее, чем вычисление квадратного корня другим методом и вычисление обратной величины с помощью деления с плавающей запятой. ^[10]Алгоритм был разработан с учетом 32-битной спецификации с плавающей запятой IEEE 754-1985 , но исследование Криса Ломонта показало, что он может быть реализован в других спецификациях с плавающей запятой. ^[11]

Преимущества в скорости , предлагаемой обратный быстрой квадратный корень ляпа пришли из обработки 32-разрядное с плавающей запятой слова ^{[примечание 2]} как целое число , а затем вычесть его из « волшебной » константы, 0x 5F3759DF. ^[1]^[12]^[13]^[14] Это целочисленное вычитание и битовый сдвиг приводит к битовому шаблону, который при повторном преобразованиикак число с плавающей запятой, является грубым приближением обратного квадратного корня входного числа. Выполняется одна итерация метода Ньютона для получения некоторой точности, и код готов. Алгоритм генерирует достаточно точные результаты с использованием уникального первого приближения для метода Ньютона ; однако он намного медленнее и менее точен, чем использование инструкции SSErsqrtss на процессорах x86, также выпущенных в 1999 году. ^[4]^[15]

Согласно стандарту C, переинтерпретация значения с плавающей запятой как целого числа путем разыменования приведенного указателя на него считается неопределенным поведением . Эту проблему можно было обойти с помощью memcpy, оставив порядок байтов в качестве основной проблемы для переносимости. Следующий код соответствует стандартам, хотя и за счет объявления дополнительной переменной: значение с плавающей запятой помещается в анонимное объединение, содержащее дополнительный 32-разрядный целочисленный элемент без знака, и доступ к этому целому числу обеспечивает побитовое представление содержимого значения с плавающей запятой.

#include  <stdint.h>float  Q_rsqrt (  число с плавающей запятой  ) { const float x2 = число * 0,5F ; const float threehalfs = 1,5F ;           союз  { float  f ; uint32_t  i ; }  conv  =  {  . f  =  число  }; конв . i  =  0x5f3759df  -  (  усл . i  >>  1  ); конв . f  * =  три половины  -  (  x2  *  усл . f  *  усл . f  ); возврат  конв . f ; }

Однако перетекание типов через объединение считается неопределенным поведением в C ++. Правильный способ сделать это в C ++ через C ++ 20 «s std::bit_cast. Это также позволяет функции работать в constexprконтексте.

#include  <cstdint>#include  <bit>constexpr  [[ nodiscard ]]  float  Q_rsqrt ( число с плавающей запятой  ) noexcept requires ( std :: numeric_limits < float > :: is_iec559 ) // (включить только в IEEE 754) { const float y = std :: bit_cast < float > ( 0x5f3759df - ( std :: bit_cast < std :: uint32_t > ( число ) >>            1 )); return  y  *  1.5f  -  (( число  *  0.5f )  *  y  *  y ); }

Пример работы [ править ]

В качестве примера, число $х = 0,15625$ может быть использована для расчета $1$ $/$ $\sqrt$ $х$ $\approx 2,52982$ . Первые шаги алгоритма проиллюстрированы ниже:

0011_1110_0010_0000_0000_0000_0000_0000 Битовая комбинация как x, так и i0001_1111_0001_0000_0000_0000_0000_0000 Сдвиг на одну позицию вправо: (i >> 1)0101_1111_0011_0111_0101_1001_1101_1111 Магическое число 0x5F3759DF0100_0000_0010_0111_0101_1001_1101_1111 Результат 0x5F3759DF - (i >> 1)

Интерпретация как 32-битное представление IEEE:

0_01111100_01000000000000000000000 1,25 × 2 ⁻³
0_00111110_00100000000000000000000 1,125 × 2 ⁻⁶⁵
0_10111110_01101110101100111011111 1,432430 ... × 2 ⁶³
0_10000000_01001110101100111011111 1,307430 ... × 2 ¹

$Повторная интерпретация$ этого последнего битового шаблона как числа с плавающей запятой дает приближение $y = 2,61486$ , что дает ошибку около 3,4%. После одной итерации метода Ньютона конечный результат $y = 2,52549$ , ошибка всего 0,17%.

Алгоритм [ править ]

Алгоритм вычисляет $1$ $/$ $\sqrt$ $х$ , выполняя следующие шаги:

Преобразует аргумент $x$ в целое число как способ вычисления приближения $log 2 ( x )$
Используйте это приближение для вычисления аппроксимации $бревна 2 (1 / \sqrt х) = -1/2 войти 2 (х)$
Псевдоним обратно в число с плавающей запятой, как способ вычисления приближения экспоненты с основанием 2
Уточните приближение, используя одну итерацию метода Ньютона.

Представление с плавающей точкой [ править ]

Поскольку этот алгоритм в значительной степени полагается на битовое представление чисел с плавающей запятой одинарной точности, здесь представлен краткий обзор этого представления. Чтобы закодировать ненулевое действительное число $x$ как число с плавающей запятой одинарной точности, первым делом нужно записать $x$ как нормализованное двоичное число: ^[16]

{\ displaystyle {\ begin {align} x & = \ pm 1.b_ {1} b_ {2} b_ {3} \ ldots \ times 2 ^ {e_ {x}} \\ & = \ pm 2 ^ {e_ { x}} (1 + m_ {x}) \ end {выровнено}}}

где показатель $e x$ является целым числом, $m x \in [0, 1)$ , и $1. b 1 b 2 b 3 ...$ двоичное представление «мантиссы» $(1 + m x)$ . Поскольку единственный бит перед точкой в мантиссе всегда равен 1, его не нужно сохранять. Из этой формы вычисляются три целых числа без знака: ^[17]

$S x$ , «бит знака», равен 0, если $x > 0$ , и 1, если $x <0$ (1 бит).
$E x = e x + B$ - "смещенная экспонента", где $B = 127$ - " смещение экспоненты "^{[примечание 3]} (8 бит)
$M x = m x \times L$ , где $L = 2 23$ ^{[примечание 4]} (23 бита)

Затем эти поля упаковываются слева направо в 32-битный контейнер. ^[18]

В качестве примера снова рассмотрим число $x = 0,15625 = 0,00101 2$ . Нормализация $x$ дает:

х = +2 -3 (1 + 0,25)

и, таким образом, три беззнаковых целочисленных поля:

$S = 0$
$E = -3 + 127 = 124 = 011111002$
$M = 0,25 \times 2 23 = 2097152 = 010000000000000000000002$

эти поля упакованы, как показано на рисунке ниже:

Преобразование в целое число как приблизительный логарифм [ править ]

Если $1$ $/$ $\sqrt$ $х$ должно было быть вычислено без компьютера или калькулятор, таблица логарифмов бы полезно, вместе с идентификатором $журнала$ $Ь$ $($ $1$ $/$ $\sqrt$ $х$ $) = -$ $1 / 2 log b (x)$ , который действителен для любой базы $b$ . Быстрый обратный квадратный корень основан на этом тождестве и на том факте, что преобразование float32 в целое число дает грубое приближение его логарифма. Вот как:

Если $x$ - положительное нормальное число :

{\ displaystyle x = 2 ^ {e_ {x}} (1 + m_ {x})}

потом

{\ displaystyle \ log _ {2} (x) = e_ {x} + \ log _ {2} (1 + m_ {x})}

и поскольку $m x \in [0, 1)$ , логарифм в правой части может быть аппроксимирован формулой ^[19]

\log _{2}(1+m_{x})\approx m_{x}+\sigma

где $σ$ - свободный параметр, используемый для настройки приближения. Например, $σ = 0$ дает точные результаты на обоих концах интервала, а $σ \approx 0,0430357$ дает оптимальное приближение (лучшее в смысле равномерной нормы ошибки).

Целое число с псевдонимом числа с плавающей запятой (синим цветом) по сравнению с масштабированным и сдвинутым логарифмом (серым цветом).

Таким образом, существует приближение

\log _{2}(x)\approx e_{x}+m_{x}+\sigma .

Интерпретация битовой последовательности чисел с плавающей запятой $x$ как целого числа $I x$ дает ^{[примечание 5]}

{\begin{aligned}I_{x}&=E_{x}L+M_{x}\\&=L(e_{x}+B+m_{x})\\&=L(e_{x}+m_{x}+\sigma +B-\sigma )\\&\approx L\log _{2}(x)+L(B-\sigma ).\end{aligned}}

Тогда оказывается, что $I x$ является масштабированной и сдвинутой кусочно-линейной аппроксимацией $log 2 (x)$ , как показано на рисунке справа. Другими словами, $log 2 (x)$ аппроксимируется как

\log _{2}(x)\approx {\frac {I_{x}}{L}}-(B-\sigma ).

Первое приближение результата [ править ]

Расчет $у = 1 / \sqrt х$ основана на идентичности

\log _{2}(y)=-{\tfrac {1}{2}}\log _{2}(x)

Используя приведенное выше приближение логарифма, примененное как к $x, так$ и к $y$ , приведенное выше уравнение дает:

{\frac {I_{y}}{L}}-(B-\sigma )\approx -{\frac {1}{2}}\left({\frac {I_{x}}{L}}-(B-\sigma )\right)

Таким образом, приближение $I y$ :

I_{y}\approx {\tfrac {3}{2}}L(B-\sigma )-{\tfrac {1}{2}}I_{x}

который записывается в коде как

i  =  0x5f3759df  -  (  i  >>  1  );

Первый член выше - это магическое число

{\tfrac {3}{2}}L(B-\sigma )={\text{0x5F3759DF}}

из чего можно заключить, что $σ \approx 0,0450466$ . Второй срок, $1 / 2 I x$ вычисляется путем сдвига битов $I x на$ одну позицию вправо. ^[20]

Метод Ньютона [ править ]

Относительная ошибка между прямым вычислением и быстрым обратным вычислением квадратного корня при выполнении 0, 1, 2, 3 и 4 итераций метода нахождения корня Ньютона. Обратите внимание, что принята двойная точность, и наименьшая представимая разница между двумя числами двойной точности достигается после выполнения 4 итераций.

С $y$ в качестве обратного квадратного корня, $f (y) = 1 / y 2 - х = 0$ . Приближение, полученное на предыдущих этапах, можно уточнить с помощью метода поиска корня, метода , который находит нуль функции . Алгоритм использует метод Ньютона : если есть приближение $y n$ для $y$ , то лучшее приближение $y n +1$ может быть вычислено, взяв $y n - f (y n) / f ' (y n)$ , Где $F ' (у п)$ является производной от $F (у)$ при $у п$ . ^[21] Для указанного выше $f (y)$ ,

y_{n+1}={\frac {y_{n}\left(3-xy_{n}^{2}\right)}{2}}

где $f (y) = 1 / y 2 - x$ и $f ' (y) = - 2 / y 3$ .

Рассмотрение $y$ как числа с плавающей запятой y = y*(threehalfs - x2*y*y);эквивалентно

y_{n+1}=y_{n}\left({\frac {3}{2}}-{\frac {x}{2}}y_{n}^{2}\right)={\frac {y_{n}\left(3-xy_{n}^{2}\right)}{2}}.

Повторяя этот шаг, используя выходной функции ( $у п + 1$ ) в качестве ввода следующей итерации, алгоритм вызывает $у$ к сходятся к обратному квадратному корню. ^[22] Для целей Quake III двигателя , была использована только одна итерация. Вторая итерация осталась в коде, но была закомментирована . ^[14]

Точность [ править ]

График, показывающий разницу между эвристическим быстрым обратным квадратным корнем и прямым обращением квадратного корня, предоставляемым libstdc . ^{[ необходима цитата ]} (Обратите внимание на шкалу журнала по обеим осям.)

Как отмечалось выше, приближение удивительно точное. Единственный график справа отображает ошибку функции (то есть ошибку аппроксимации после того, как она была улучшена путем выполнения одной итерации метода Ньютона) для входных данных, начинающихся с 0,01, где стандартная библиотека дает в результате 10,0 , в то время как InvSqrt () дает 9,982522, что составляет разницу 0,017479, или 0,175% от истинного значения, 10. С этого момента абсолютная ошибка только уменьшается, в то время как относительная ошибка остается в тех же пределах во всех порядках величины.

История [ править ]

Исходный код Quake III не был выпущен до QuakeCon 2005 , но копии кода быстрого вычисления обратного квадратного корня появились в Usenet и других форумах уже в 2002 или 2003 годах. ^[1] Первоначальные предположения указывали на Джона Кармака как на вероятного автора книги. код, но он возразил и предположил, что его написал Терье Матисен, опытный программист на ассемблере, который ранее помогал id Software с оптимизацией Quake . Матисен написал реализацию подобного фрагмента кода в конце 1990-х, но первоначальные авторы оказались намного дальше в истории компьютерной 3D-графики с реализацией Гэри Таролли для SGI Indigo.как возможное самое раннее известное использование. Рис Соммефельдт пришел к выводу, что оригинальный алгоритм был разработан Грегом Уолшем из Ardent Computer в консультации с Кливом Молером , создателем MATLAB . ^[23] Клив Молер узнал об этом трюке из кода, написанного Уильямом Каханом и К.С. Нг в Беркли примерно в 1986 году. ^[24] Джим Блинн также продемонстрировал простое приближение обратного квадратного корня в столбце 1997 года для IEEE Computer Graphics and Applications . ^[25]^[26] Пол Кинни реализовал быстрый метод для компьютера серии FPS T ^[27]Примерно в 1986 году. Система включала аппаратное обеспечение векторных вычислений с плавающей запятой, которое не было богато целочисленными операциями. Значения с плавающей запятой были перемещены, чтобы можно было манипулировать для создания начального приближения.

Последующие улучшения [ править ]

Магическое число [ править ]

Точно неизвестно, как было определено точное значение магического числа. Крис Lomont разработал функцию , чтобы минимизировать ошибку аппроксимации , выбирая магическое число $R$ по всему диапазону. Сначала он вычислил оптимальную константу для шага линейного приближения как 0x5F37642F , близкую к 0x5F3759DF , но эта новая константа дала немного меньшую точность после одной итерации метода Ньютона. ^[28] Затем Ломонт искал константу, оптимальную даже после одной и двух итераций по Ньютону, и нашел 0x5F375A86 , что более точно, чем оригинал на каждой стадии итерации. ^[28]В заключение он спросил, было ли выбрано точное значение исходной постоянной путем вывода или методом проб и ошибок . ^[29] Ломонт сказал, что магическим числом для 64-битного типа размера IEEE754 является 0x5FE6EC85E7DE30DA , но позже Мэтью Робертсон показал, что оно точно равно 0x5FE6EB50C7B537A9 . ^[30]

Ян Кадлец уменьшил относительную ошибку еще в 2,7 раза за счет корректировки констант в одной итерации метода Ньютона ^[31], получив после исчерпывающего поиска на

конв . i  =  0x5F1FFFF9  -  (  усл . i  >>  1  ); конв . f  * =  0,703952253f  *  (  2,38924456f  -  x  *  усл . f  *  усл . f  ); возврат  конв . f ;

Полный математический анализ для определения магического числа теперь доступен для чисел с плавающей запятой одинарной точности. ^[32]

Нулевое обнаружение [ править ]

Промежуточным звеном к использованию одной и двух итераций метода Ньютона с точки зрения скорости и точности является одна итерация метода Галлея . В этом случае метод Галлея эквивалентен применению метода Ньютона с исходной формулой . Затем шаг обновления $f(y)={\frac {1}{y^{1/2}}}-xy^{3/2}=0$

y_{n+1}=y_{n}-{\frac {f(y_{n})}{f'(y_{n})}}=y_{n}\left({\frac {3+xy_{n}^{2}}{1+3xy_{n}^{2}}}\right),

где реализация должна вычисляться только один раз через временную переменную. $xy_{n}^{2}$

См. Также [ править ]

Методы вычисления квадратных корней § Приближения, зависящие от представления с плавающей запятой
Магическое число

Заметки [ править ]

^ В 2000 году на китайском форуме разработчиков CSDN шла дискуссия^[2].
^ Использование типаlongснижает переносимость этого кода в современных системах. Для правильного выполнения кода онsizeof(long)должен быть 4 байта, иначе могут возникнуть отрицательные результаты. Во многих современных 64-битных системахsizeof(long)это 8 байт. Более портативная заменаint32_t.
^ $E x$ должен быть в диапазоне $[1, 254],$ чтобы $x$ можно было представить как нормальное число .
^ Единственные действительные числа, которые могут быть представлены точно как числа с плавающей запятой, - это те, для которых $M x$ является целым числом. Другие числа можно представить только приблизительно путем их округления до ближайшего точно представимого числа.
^ $S x = 0,$ поскольку $x > 0$ .

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

^ a b c d Sommefeldt, Rys (29 ноября 2006 г.). "Происхождение быстрого InvSqrt () Quake3" . Beyond3D . Проверено 12 февраля 2009 .
^ «Обсуждение на CSDN» . Архивировано из оригинала на 2015-07-02.
^ Munafo, Роберт. «Примечательные свойства конкретных чисел» . mrob.com . Архивировано 16 ноября 2018 года.
^ a b Раскин, Элан (16.10.2009). «Время квадратный корень» . Требуется некоторая сборка . Проверено 7 мая 2015 .
^ feilipu. «z88dk - это набор инструментов для разработки программного обеспечения, предназначенный для компьютеров 8080 и z80» .
^ Blinn 2003 , стр. 130.
Перейти ↑ Middendorf 2007 , pp. 155–164.
^ "quake3-1.32b / code / game / q_math.c" . Quake III Arena . id Software . Проверено 21 января 2017 .
^ Eberly 2001 , стр. 504.
^ Lomont 2003 , стр. 1.
^ Lomont 2003 .
^ Lomont 2003 , стр. 3.
^ McEniry 2007 , стр. 2, 16.
^ a b Эберли 2001 , стр. 2.
^ Туман, Агнер. «Списки задержек инструкций, пропускной способности и сбоев микроопераций для процессоров Intel, AMD и VIA» (PDF) . Проверено 8 сентября 2017 .
Перейти ↑ Goldberg 1991 , p. 7.
↑ Голдберг, 1991 , стр. 15–20.
Перейти ↑ Goldberg 1991 , p. 16.
^ McEniry 2007 , стр. 3.
^ Хеннесси и Паттерсон 1998 , стр. 305.
^ Харди 1908 , стр. 323.
^ McEniry 2007 , стр. 6.
^ Sommefeldt, Рысь (2006-12-19). «Происхождение быстрого InvSqrt () в Quake3 - Часть вторая» . Beyond3D . Проверено 19 апреля 2008 .
^ Молер, Клив. «Симплектическая космическая война» . MATLAB Central - угол Клив . MATLAB . Проверено 21 июля 2014 .
^ Blinn 1997 , стр. 80-84.
^ "Реализация sqrt в fdlibm" .
^ Фаззари, Род; Майлз, Дуг; Карлайл, Брэд; Грошонг, Джадсон (1988). «Новое поколение аппаратного и программного обеспечения для серии FPS T». Труды конференции по массивам 1988 : 75–89.
^ а б Ломонт 2003 , стр. 10.
^ Lomont 2003 , стр. 10-11.
↑ Мэтью Робертсон (24 апреля 2012 г.). «Краткая история InvSqrt» (PDF) . UNBSJ.
^ Кадлек Ян (2010). «Řrřlog :: Улучшение быстрого обратного квадратного корня» (личный блог) . Проверено 14 декабря 2020 .
^ Мороз и др. 2018 .

Библиография [ править ]

Блинн, Джим (июль 1997 г.). «Уловки с плавающей точкой». Компьютерная графика и приложения IEEE . 17 (4): 80. DOI : 10,1109 / 38,595279 .
Блинн, Джим (2003). Уголок Джима Блинна: Обозначения, условные обозначения . Морган Кауфманн. ISBN 1-55860-860-5.
Эберли, Дэвид (2001). Дизайн игрового движка 3D . Морган Кауфманн. ISBN 978-1-55860-593-0.
Гольдберг, Дэвид (1991). «Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой». ACM Computing Surveys . 23 (1): 5–48. DOI : 10.1145 / 103162.103163 . S2CID 222008826 .
Харди, Годфри (1908). Курс чистой математики . Кембридж, Великобритания : Издательство Кембриджского университета . ISBN 0-521-72055-9.
Хеннесси, Джон; Паттерсон, Дэвид А. (1998). Компьютерная организация и дизайн (2-е изд.). Сан-Франциско, Калифорния: Издательство Морган Кауфманн. ISBN 978-1-55860-491-9.
Ломонт, Крис (февраль 2003 г.). «Быстрый обратный квадратный корень» (PDF) . Проверено 13 февраля 2009 .
МакЭнири, Чарльз (август 2007 г.). «Математика, лежащая в основе кода функции быстрого обратного квадратного корня» (PDF) . Архивировано из оригинального (PDF) 11 мая 2015 года.
Миддендорф, Ларс; Мюльбауэр, Феликс; Умлауф, Джордж; Бодба, Кристоф (1 июня 2007 г.). «Встроенный вершинный шейдер в ПЛИС» (PDF) . В Реттберге, Ачине (ред.). Проектирование встроенных систем: темы, методы и тенденции . Рабочая конференция IFIP TC10: Международный симпозиум по встроенным системам (IESS). и другие. Ирвин, Калифорния : Спрингер. DOI : 10.1007 / 978-0-387-72258-0_14 . ISBN 978-0-387-72257-3. Архивировано (PDF) из оригинала на 2019-05-01.
Стригель, Джейсон (2008-12-04). «Быстрый обратный квадратный корень Quake» . Hackszine . O'Reilly Media . Архивировано из оригинала на 2009-02-15 . Проверено 7 января 2013 .
IEEE Computer Society (1985), 754-1985 - Стандарт IEEE для двоичной арифметики с плавающей запятой , Институт инженеров по электротехнике и электронике
Мороз, Леонид В .; Walczyk, Cezary J .; Гринчишин, Андрей; Холимат, Виджай; Цеслински, Ян Л. (январь 2018 г.). «Быстрое вычисление обратного квадратного корня с использованием аналитического подхода магической константы». Прикладная математика и вычисления . Elsevier Science Inc. 316 (C): 245–255. arXiv : 1603.04483 . DOI : 10.1016 / j.amc.2017.08.025 . S2CID 7494112 .

Дальнейшее чтение [ править ]

Кушнер, Дэвид (август 2002). «Волшебство Ид». IEEE Spectrum . 39 (8): 42–47. DOI : 10.1109 / MSPEC.2002.1021943 .

Внешние ссылки [ править ]

0x5f3759df , дальнейшие исследования точности и обобщения алгоритма Кристиана Плеснера Хансена
Происхождение быстрого InvSqrt из Quake3 ()
Исходный код Quake III Arena
Реализация InvSqrt в DESMOS
«Быстрый обратный квадратный корень - алгоритм Quake III» ( YouTube )

[3] В 2000 году на китайском форуме разработчиков CSDN шла дискуссия^[2].

[13] Использование типаlongснижает переносимость этого кода в современных системах. Для правильного выполнения кода онsizeof(long)должен быть 4 байта, иначе могут возникнуть отрицательные результаты. Во многих современных 64-битных системахsizeof(long)это 8 байт. Более портативная заменаint32_t.

[20] $E x$ должен быть в диапазоне $[1, 254],$ чтобы $x$ можно было представить как нормальное число .

[21] Единственные действительные числа, которые могут быть представлены точно как числа с плавающей запятой, - это те, для которых $M x$ является целым числом. Другие числа можно представить только приблизительно путем их округления до ближайшего точно представимого числа.

[24] $S x = 0,$ поскольку $x > 0$ .

[Beyond3D-1] Sommefeldt, Rys (29 ноября 2006 г.). "Происхождение быстрого InvSqrt () Quake3" . Beyond3D . Проверено 12 февраля 2009 .

[csdn-2] «Обсуждение на CSDN» . Архивировано из оригинала на 2015-07-02.

[mrob-4] Munafo, Роберт. «Примечательные свойства конкретных чисел» . mrob.com . Архивировано 16 ноября 2018 года.

[ruskin-5] Раскин, Элан (16.10.2009). «Время квадратный корень» . Требуется некоторая сборка . Проверено 7 мая 2015 .

[z88dk-6] u. «z88dk - это набор инструментов для разработки программного обеспечения, предназначенный для компьютеров 8080 и z80» .

[FOOTNOTEBlinn2003130-7] Blinn 2003 , стр. 130.

[FOOTNOTEMiddendorf2007155–164-8] Перейти ↑ Middendorf 2007 , pp. 155–164.

[quakesrc-9] "quake3-1.32b / code / game / q_math.c" . Quake III Arena . id Software . Проверено 21 января 2017 .

[FOOTNOTEEberly2001504-10] Eberly 2001 , стр. 504.

[FOOTNOTELomont20031-11] Lomont 2003 , стр. 1.

[FOOTNOTELomont2003-12] Lomont 2003 .

[FOOTNOTELomont20033-14] Lomont 2003 , стр. 3.

[FOOTNOTEMcEniry20072,_16-15] McEniry 2007 , стр. 2, 16.

[FOOTNOTEEberly20012-16] Эберли 2001 , стр. 2.

[agner-17] Туман, Агнер. «Списки задержек инструкций, пропускной способности и сбоев микроопераций для процессоров Intel, AMD и VIA» (PDF) . Проверено 8 сентября 2017 .

[FOOTNOTEGoldberg19917-18] Перейти ↑ Goldberg 1991 , p. 7.

[FOOTNOTEGoldberg199115&ndash;20-19] Голдберг, 1991 , стр. 15–20.

[FOOTNOTEGoldberg199116-22] Перейти ↑ Goldberg 1991 , p. 16.

[FOOTNOTEMcEniry20073-23] McEniry 2007 , стр. 3.

[FOOTNOTEHennesseyPatterson1998305-25] Хеннесси и Паттерсон 1998 , стр. 305.

[FOOTNOTEHardy1908323-26] Харди 1908 , стр. 323.

[FOOTNOTEMcEniry20076-27] McEniry 2007 , стр. 6.

[Beyond3Dp2-28] Sommefeldt, Рысь (2006-12-19). «Происхождение быстрого InvSqrt () в Quake3 - Часть вторая» . Beyond3D . Проверено 19 апреля 2008 .

[MolerResp-29] Молер, Клив. «Симплектическая космическая война» . MATLAB Central - угол Клив . MATLAB . Проверено 21 июля 2014 .

[FOOTNOTEBlinn199780–84-30] Blinn 1997 , стр. 80-84.

[fdlibm-31] "Реализация sqrt в fdlibm" .

[32] Фаззари, Род; Майлз, Дуг; Карлайл, Брэд; Грошонг, Джадсон (1988). «Новое поколение аппаратного и программного обеспечения для серии FPS T». Труды конференции по массивам 1988 : 75–89.

[FOOTNOTELomont200310-33] а б Ломонт 2003 , стр. 10.

[FOOTNOTELomont200310–11-34] Lomont 2003 , стр. 10-11.

[robertson-35] Мэтью Робертсон (24 апреля 2012 г.). «Краткая история InvSqrt» (PDF) . UNBSJ.

[36] Кадлек Ян (2010). «Řrřlog :: Улучшение быстрого обратного квадратного корня» (личный блог) . Проверено 14 декабря 2020 .

[FOOTNOTEMorozWalczykHrynchyshynHolimath2018-37] Мороз и др. 2018 .

[1]