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

В расчетах освещения и отражения, как в видеоигре OpenArena , используется быстрый код обратного квадратного корня для вычисления углов падения и отражения.

Быстрый обратный квадратный корень , иногда называемый Быстрый InvSqrt() или шестнадцатеричная константа 0x5F3759DF — это алгоритм, который оценивает ${\textstyle {\frac {1}{\sqrt {x}}}}$, обратное (или мультипликативное обратное) квадратному корню из 32-битного с плавающей запятой . числа $x$ в формате с плавающей запятой IEEE 754 . Алгоритм наиболее известен благодаря своей реализации в 1999 году в Quake III Arena , видеоигре- шутере от первого лица, в значительной степени основанной на 3D-графике . С последующими усовершенствованиями аппаратного обеспечения, особенно с x86 SSE. инструкцией rsqrtss, этот алгоритм вообще не лучший выбор для современных компьютеров, хотя это остается интересным историческим примером.

Алгоритм принимает на вход 32-битное число с плавающей запятой и сохраняет уменьшенное пополам значение для дальнейшего использования. Затем, рассматривая биты, представляющие число с плавающей запятой, как 32-битное целое число, выполняется логический сдвиг вправо на один бит и результат вычитается из числа. 0x 5F3759DF , который представляет собой представление с плавающей запятой приближения ${\textstyle {\sqrt {2^{127}}}}$. Это приводит к первому приближению обратного квадратного корня входных данных. Снова рассматривая биты как числа с плавающей запятой, он запускает одну итерацию метода Ньютона , давая более точное приближение.

История

Уильям Кахан и К.К. Нг из Беркли в мае 1986 года написали неопубликованную статью, описывающую, как вычислить квадратный корень, используя методы битовой игры с последующими итерациями Ньютона. В конце 1980-х годов Клив Молер из Ardent Computer. об этой технике узнал и передал его своему коллеге Грегу Уолшу. Грег Уолш разработал ныне известный константный и быстрый алгоритм обратного квадратного корня. Гэри Таролли консультировал Kubota, компанию, которая в то время финансировала Ardent, и, вероятно, представил алгоритм в 3dfx Interactive примерно в 1994 году.

Джим Блинн продемонстрировал простую аппроксимацию обратного квадратного корня в колонке журнала IEEE Computer Graphics and Applications в 1997 году . Обратное проектирование других современных 3D-видеоигр выявило вариацию алгоритма в игре от Activision 1997 года Interstate '76 .

Quake III Arena , видеоигра- шутер от первого лица , была выпущена в 1999 году компанией id Software и использовала этот алгоритм. Брайан Хук, возможно, перенес этот алгоритм из 3dfx в id Software. Обсуждение кода появилось на китайском форуме разработчиков CSDN в 2000 году. а Usenet и форум gamedev.net широко распространили код в 2002 и 2003 годах. Возникли предположения относительно того, кто написал алгоритм и как была получена константа; некоторые предполагали, что это Джон Кармак . Quake III был Полный исходный код представлен на QuakeCon 2005 , но ответов на него не было. Ответ на вопрос об авторстве был получен в 2006 году, когда Грег Уолш связался с Beyond3D, поскольку их предположения стали популярными на Slashdot.

В 2007 году алгоритм был реализован в некоторых специализированных аппаратных вершинных шейдерах с использованием программируемых пользователем вентильных матриц (FPGA).

Мотивация

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

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

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

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

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

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

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

– нормированный (единичный) вектор. Замена ${\textstyle \|{\boldsymbol {v}}\|}$, уравнение также можно записать как:

${\boldsymbol {\hat {v}}}={\frac {\boldsymbol {v}}{\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}}$

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

${\boldsymbol {\hat {v}}}={\boldsymbol {v}}\,{\frac {1}{\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}}$

где член дроби представляет собой обратный квадратный корень из $v_{1}^{2}+v_{2}^{2}+v_{3}^{2}$.

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

Обзор кода

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

float Q_rsqrt(float number)
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;                       // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

  return y;
}

В то время общий метод вычисления обратного квадратного корня заключался в вычислении приближения для ${\textstyle {\frac {1}{\sqrt {x}}}}$, затем пересмотрите это приближение с помощью другого метода, пока оно не окажется в допустимом диапазоне ошибок фактического результата. Распространенные программные методы начала 1990-х годов основывались на справочной таблице . Ключом к быстрому обратному квадратному корню было непосредственное вычисление аппроксимации с использованием структуры чисел с плавающей запятой, что оказалось быстрее, чем поиск в таблице. Алгоритм оказался примерно в четыре раза быстрее, чем вычисление квадратного корня другим методом и вычисление обратной величины посредством деления с плавающей запятой. Алгоритм был разработан с учетом спецификации 32-битных чисел с плавающей запятой стандарта IEEE 754-1985 , но исследование Криса Ломонта показало, что он может быть реализован и в других спецификациях чисел с плавающей запятой.

Преимущества в скорости, обеспечиваемые быстрым трюком с обратным квадратным корнем, возникли благодаря обработке 32-битного с плавающей запятой . слова как целое число , а затем вычитая его из « магической » константы, 0x5F3759DF ​ . Это вычитание целого числа и битовый сдвиг приводят к образованию битового шаблона, который, если его переопределить как число с плавающей запятой, является грубым приближением обратного квадратного корня из числа. Для достижения некоторой точности выполняется одна итерация метода Ньютона, и код готов. Алгоритм генерирует достаточно точные результаты, используя уникальное первое приближение метода Ньютона ; однако это намного медленнее и менее точно, чем использование SSE . инструкции rsqrtss на процессорах x86, также выпущенных в 1999 году.

Рабочий пример

Например, число $x=0.15625$ можно использовать для расчета ${\textstyle {\frac {1}{\sqrt {x}}}\approx 2.52982}$. Первые шаги алгоритма показаны ниже:

0011_1110_0010_0000_0000_0000_0000_0000  Bit pattern of both x and i
0001_1111_0001_0000_0000_0000_0000_0000  Shift right one position: (i >> 1)
0101_1111_0011_0111_0101_1001_1101_1111  The magic number 0x5F3759DF
0100_0000_0010_0111_0101_1001_1101_1111  The result of 0x5F3759DF - (i >> 1)

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

0_01111100_01000000000000000000000  1.25 × 2−3
0_00111110_00100000000000000000000  1.125 × 2−65
0_10111110_01101110101100111011111  1.432430... × 263
0_10000000_01001110101100111011111  1.307430... × 21

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

Как избежать неопределенного поведения

Согласно стандарту C, переинтерпретация значения с плавающей запятой как целого числа путем приведения и разыменования указателя на него недопустима ( неопределенное поведение ). Другой способ — поместить значение с плавающей запятой в анонимное объединение , содержащее дополнительный 32-битный целочисленный элемент без знака, и доступ к этому целому числу обеспечивает представление на уровне битов содержимого значения с плавающей запятой. Однако игра слов типов через объединение также является неопределенным поведением в C++.

# include <stdint.h> // uint32_t

float Q_rsqrt(float number)
{
  union {
    float    f;
    uint32_t i;
  } conv = { .f = number };
  conv.i  = 0x5f3759df - (conv.i >> 1);
  conv.f *= 1.5F - (number * 0.5F * conv.f * conv.f);
  return conv.f;
}

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

import std;

constexpr std::float32_t Q_rsqrt(std::float32_t number) noexcept
{
  const auto y = std::bit_cast<std::float32_t>(
    0x5f3759df - (std::bit_cast<std::uint32_t>(number) >> 1));
  return y * (1.5f32 - (number * 0.5f32 * y * y));
}

Алгоритм

Алгоритм вычисляет ${\textstyle {\frac {1}{\sqrt {x}}}}$ выполнив следующие шаги:

1. Псевдоним аргумента $x$ в целое число как способ вычисления приближения двоичного логарифма ${\textstyle \log _{2}(x)}$
2. Используйте это приближение, чтобы вычислить приближение ${\textstyle \log _{2}\left({\frac {1}{\sqrt {x}}}\right)=-{\frac {1}{2}}\log _{2}(x)}$
3. Псевдоним обратного значения с плавающей запятой, как способ вычисления аппроксимации экспоненты по основанию 2.
4. Уточните приближение, используя одну итерацию метода Ньютона.

Представление с плавающей запятой

Основная статья: Формат с плавающей запятой одинарной точности

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

${\begin{aligned}x&=\pm 1.b_{1}b_{2}b_{3}\ldots \times 2^{e_{x}}\end{aligned}}$

где показатель степени ${\textstyle e_{x}}$ является целым числом, и ${\textstyle 1.b_{1}b_{2}b_{3}\ldots }$ является двоичным представлением мантиссы . Поскольку единственный бит перед точкой в ​​мантиссе всегда равен 1, его не нужно сохранять. Уравнение можно переписать как:

${\begin{aligned}x&=\pm 2^{e_{x}}(1+m_{x})\end{aligned}}$

где ${\textstyle m_{x}}$ означает ${\textstyle 0.b_{1}b_{2}b_{3}\ldots }$, так ${\textstyle m_{x}\in [0,1)}$. Из этой формы вычисляются три целых числа без знака:

• ${\textstyle S_{x}}$, «знаковый бит» $0$ если $x$ является положительным и $1$ отрицательный или нулевой (1 бит)
• ${\textstyle E_{x}=e_{x}+B}$ - «смещенный показатель степени», где $B=127$ это « смещение показателя » (8 бит)
• ${\textstyle M_{x}=m_{x}\times L}$, где ${\textstyle L=2^{23}}$ (23 бита)

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

В качестве примера рассмотрим еще раз число $x=0.15625=0.00101_{2}$. Нормализация $x$ дает:

${\textstyle x=+2^{-3}(1+0.25)}$

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

• $S=0$
• $E=-3+127=124=0111\ 1100_{2}$
• $M=0.25\times 2^{23}=2\ 097\ 152=0010\ 0000\ 0000\ 0000\ 0000\ 0000_{2}$

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

Псевдоним целого числа как приближенный логарифм

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

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

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

затем

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

и поскольку $m_{x}\in [0,1)$, логарифм в правой части можно аппроксимировать выражением

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

где $\sigma$ — свободный параметр, используемый для настройки аппроксимации. Например, $\sigma =0$ дает точные результаты на обоих концах интервала, в то время как ${\textstyle \sigma ={\frac {1}{2}}-{\frac {1+\ln(\ln(2))}{2\ln(2)}}\approx 0.0430357}$ дает оптимальное приближение (лучшее в смысле равномерной нормы ошибки). Однако это значение не используется алгоритмом, поскольку не учитывает последующие шаги.

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

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

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

Интерпретация битового шаблона с плавающей запятой $x$ как целое число $I_{x}$ урожайность

${\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 ).$

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

Расчет ${\textstyle y={\frac {1}{\sqrt {x}}}}$ основано на тождестве

$\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 )={\mathtt {0x5F3759DF}}$

из чего можно сделать вывод, что $\sigma \approx 0.0450466$. Второй срок, ${\frac {1}{2}}I_{x}$, вычисляется путем сдвига битов $I_{x}$ на одну позицию вправо.

метод Ньютона

Основная статья: метод Ньютона

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

С $y$ как обратный квадратный корень, $f(y)={\frac {1}{y^{2}}}-x=0$. Аппроксимация, полученная на предыдущих этапах, может быть уточнена с помощью метода поиска корня — метода, который находит ноль функции . Алгоритм использует метод Ньютона : если есть приближение, $y_{n}$ для $y$, то лучшее приближение $y_{n+1}$ можно вычислить, взяв $y_{n}-{\frac {f(y_{n})}{f'(y_{n})}}$, где $f'(y_{n})$ является производной от $f(y)$ в $y_{n}$. Для вышесказанного $f(y)$,

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

где $f(y)={\frac {1}{y^{2}}}-x$ и $f'(y)=-{\frac {2}{y^{3}}}$.

Лечение $y$ как число с плавающей запятой, y = y*(threehalfs - x/2*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}}.$

Повторив этот шаг, используя выходные данные функции ( $y_{n+1}$) в качестве входных данных следующей итерации алгоритм вызывает $y$ сходиться к обратному квадратному корню. Для целей Quake III движка использовалась только одна итерация. Вторая итерация осталась в коде, но была закомментирована .

Точность

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

Последующие улучшения

Магическое число

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

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

conv.i = 0x5F1FFFF9 - ( conv.i >> 1 );
conv.f *= 0.703952253f * ( 2.38924456f - x * conv.f * conv.f );
return conv.f;

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

Нулевой результат

Промежуточным по сравнению с использованием одной и двух итераций метода Ньютона с точки зрения скорости и точности является одна итерация метода Галлея . В этом случае метод Галлея эквивалентен применению метода Ньютона с исходной формулой $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}$ только один раз, через временную переменную.

Устаревание

Последующие дополнения производителей оборудования сделали этот алгоритм по большей части излишним. Например, на x86 Intel представила SSE инструкцию rsqrtss в 1999 году. В тесте Intel Core 2 2009 года эта инструкция занимала 0,85 нс на одно число с плавающей запятой по сравнению с 3,54 нс для быстрого алгоритма обратного квадратного корня и имела меньшую ошибку.

Некоторые недорогие встроенные системы не имеют специализированных инструкций по извлечению квадратного корня. Однако производители этих систем обычно предоставляют тригонометрические и другие математические библиотеки, основанные на таких алгоритмах, как CORDIC .

См. также

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

Ссылки

Библиография

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

Дальнейшее чтение

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

Внешние ссылки

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