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

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

Алгоритм

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

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

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

История

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

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

Так как значение <math>{2}^{128} = nan </math>

<math>FloatToHex({2}^{128}*0,5)=7F000000 </math>

<math>13043817825332782212 = \sqrt{170141183460469231731687303715884105728} </math>

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

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

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

Мотивация

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

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

<math>\|\boldsymbol{v}\| = \sqrt{{v_1}^2+{v_2}^2+{v_3}^2}</math> — это евклидова норма вектора, аналог Евклидова расстояния между двумя точками в пространстве.

<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \|\boldsymbol{v}\|</math> — это нормализованный единичный вектор. Вычисленное <math>{v_1}^2+{v_2}^2+{v_3}^2</math> обозначим как <math>\boldsymbol{x}</math>,

<math>\boldsymbol{\hat{v}} = \boldsymbol{v} / \sqrt{x}</math>, определяет соотношение единичного вектора и обратного квадратного корня от <math>x</math>.

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

Ссылки

• [www.codemaestro.com/reviews/9 Magical Square Root Implementation In Quake III]
• C. Lomont, [www2.mrbrklyn.com/resources/InvSqrt.pdf Fast inverse square root], Technical Report, 2003.
• [shelfflag.com/rsqrt.pdf A Brief History of InvSqrt] by Matthew Robertson
• [blog.quenta.org/2012/09/0x5f3759df.html 0x5f3759df], further investigations into accuracy and generalizability of the algorithm by Christian Plesner Hansen

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Быстрый обратный квадратный корень

Муж посмотрел на нее с таким видом, как будто он был удивлен, заметив, что кто то еще, кроме его и Пьера, находился в комнате; и он с холодною учтивостью вопросительно обратился к жене:
– Чего ты боишься, Лиза? Я не могу понять, – сказал он.
– Вот как все мужчины эгоисты; все, все эгоисты! Сам из за своих прихотей, Бог знает зачем, бросает меня, запирает в деревню одну.
– С отцом и сестрой, не забудь, – тихо сказал князь Андрей.
– Всё равно одна, без моих друзей… И хочет, чтобы я не боялась.
Тон ее уже был ворчливый, губка поднялась, придавая лицу не радостное, а зверское, беличье выраженье. Она замолчала, как будто находя неприличным говорить при Пьере про свою беременность, тогда как в этом и состояла сущность дела.
– Всё таки я не понял, de quoi vous avez peur, [Чего ты боишься,] – медлительно проговорил князь Андрей, не спуская глаз с жены.
Княгиня покраснела и отчаянно взмахнула руками.
– Non, Andre, je dis que vous avez tellement, tellement change… [Нет, Андрей, я говорю: ты так, так переменился…]
– Твой доктор велит тебе раньше ложиться, – сказал князь Андрей. – Ты бы шла спать.
Княгиня ничего не сказала, и вдруг короткая с усиками губка задрожала; князь Андрей, встав и пожав плечами, прошел по комнате.
Пьер удивленно и наивно смотрел через очки то на него, то на княгиню и зашевелился, как будто он тоже хотел встать, но опять раздумывал.
– Что мне за дело, что тут мсье Пьер, – вдруг сказала маленькая княгиня, и хорошенькое лицо ее вдруг распустилось в слезливую гримасу. – Я тебе давно хотела сказать, Andre: за что ты ко мне так переменился? Что я тебе сделала? Ты едешь в армию, ты меня не жалеешь. За что?
– Lise! – только сказал князь Андрей; но в этом слове были и просьба, и угроза, и, главное, уверение в том, что она сама раскается в своих словах; но она торопливо продолжала:
– Ты обращаешься со мной, как с больною или с ребенком. Я всё вижу. Разве ты такой был полгода назад?
– Lise, я прошу вас перестать, – сказал князь Андрей еще выразительнее.
Пьер, всё более и более приходивший в волнение во время этого разговора, встал и подошел к княгине. Он, казалось, не мог переносить вида слез и сам готов был заплакать.
– Успокойтесь, княгиня. Вам это так кажется, потому что я вас уверяю, я сам испытал… отчего… потому что… Нет, извините, чужой тут лишний… Нет, успокойтесь… Прощайте…
Князь Андрей остановил его за руку.
– Нет, постой, Пьер. Княгиня так добра, что не захочет лишить меня удовольствия провести с тобою вечер.
– Нет, он только о себе думает, – проговорила княгиня, не удерживая сердитых слез.
– Lise, – сказал сухо князь Андрей, поднимая тон на ту степень, которая показывает, что терпение истощено.
Вдруг сердитое беличье выражение красивого личика княгини заменилось привлекательным и возбуждающим сострадание выражением страха; она исподлобья взглянула своими прекрасными глазками на мужа, и на лице ее показалось то робкое и признающееся выражение, какое бывает у собаки, быстро, но слабо помахивающей опущенным хвостом.
– Mon Dieu, mon Dieu! [Боже мой, Боже мой!] – проговорила княгиня и, подобрав одною рукой складку платья, подошла к мужу и поцеловала его в лоб.
– Bonsoir, Lise, [Доброй ночи, Лиза,] – сказал князь Андрей, вставая и учтиво, как у посторонней, целуя руку.


Друзья молчали. Ни тот, ни другой не начинал говорить. Пьер поглядывал на князя Андрея, князь Андрей потирал себе лоб своею маленькою рукой.
– Пойдем ужинать, – сказал он со вздохом, вставая и направляясь к двери.
Они вошли в изящно, заново, богато отделанную столовую. Всё, от салфеток до серебра, фаянса и хрусталя, носило на себе тот особенный отпечаток новизны, который бывает в хозяйстве молодых супругов. В середине ужина князь Андрей облокотился и, как человек, давно имеющий что нибудь на сердце и вдруг решающийся высказаться, с выражением нервного раздражения, в каком Пьер никогда еще не видал своего приятеля, начал говорить:
– Никогда, никогда не женись, мой друг; вот тебе мой совет: не женись до тех пор, пока ты не скажешь себе, что ты сделал всё, что мог, и до тех пор, пока ты не перестанешь любить ту женщину, какую ты выбрал, пока ты не увидишь ее ясно; а то ты ошибешься жестоко и непоправимо. Женись стариком, никуда негодным… А то пропадет всё, что в тебе есть хорошего и высокого. Всё истратится по мелочам. Да, да, да! Не смотри на меня с таким удивлением. Ежели ты ждешь от себя чего нибудь впереди, то на каждом шагу ты будешь чувствовать, что для тебя всё кончено, всё закрыто, кроме гостиной, где ты будешь стоять на одной доске с придворным лакеем и идиотом… Да что!…
Он энергически махнул рукой.
Пьер снял очки, отчего лицо его изменилось, еще более выказывая доброту, и удивленно глядел на друга.
– Моя жена, – продолжал князь Андрей, – прекрасная женщина. Это одна из тех редких женщин, с которою можно быть покойным за свою честь; но, Боже мой, чего бы я не дал теперь, чтобы не быть женатым! Это я тебе одному и первому говорю, потому что я люблю тебя.
Князь Андрей, говоря это, был еще менее похож, чем прежде, на того Болконского, который развалившись сидел в креслах Анны Павловны и сквозь зубы, щурясь, говорил французские фразы. Его сухое лицо всё дрожало нервическим оживлением каждого мускула; глаза, в которых прежде казался потушенным огонь жизни, теперь блестели лучистым, ярким блеском. Видно было, что чем безжизненнее казался он в обыкновенное время, тем энергичнее был он в эти минуты почти болезненного раздражения.
– Ты не понимаешь, отчего я это говорю, – продолжал он. – Ведь это целая история жизни. Ты говоришь, Бонапарте и его карьера, – сказал он, хотя Пьер и не говорил про Бонапарте. – Ты говоришь Бонапарте; но Бонапарте, когда он работал, шаг за шагом шел к цели, он был свободен, у него ничего не было, кроме его цели, – и он достиг ее. Но свяжи себя с женщиной – и как скованный колодник, теряешь всякую свободу. И всё, что есть в тебе надежд и сил, всё только тяготит и раскаянием мучает тебя. Гостиные, сплетни, балы, тщеславие, ничтожество – вот заколдованный круг, из которого я не могу выйти. Я теперь отправляюсь на войну, на величайшую войну, какая только бывала, а я ничего не знаю и никуда не гожусь. Je suis tres aimable et tres caustique, [Я очень мил и очень едок,] – продолжал князь Андрей, – и у Анны Павловны меня слушают. И это глупое общество, без которого не может жить моя жена, и эти женщины… Ежели бы ты только мог знать, что это такое toutes les femmes distinguees [все эти женщины хорошего общества] и вообще женщины! Отец мой прав. Эгоизм, тщеславие, тупоумие, ничтожество во всем – вот женщины, когда показываются все так, как они есть. Посмотришь на них в свете, кажется, что что то есть, а ничего, ничего, ничего! Да, не женись, душа моя, не женись, – кончил князь Андрей.