Fast inverse square root (original) (raw)
Бы́стрый обра́тный квадра́тный ко́рень (также быстрый InvSqrt или 0x5F3759DF по используемой «магической» константе, в десятичной системе 1 597 463 007) — это быстрый приближённый алгоритм вычисления обратного квадратного корня для положительных 32-битных чисел с плавающей запятой. Алгоритм использует целочисленные операции «вычесть» и «битовый сдвиг», а также дробные «вычесть» и «умножить» — без медленных операций «разделить» и «квадратный корень». Несмотря на «хакерство» на битовом уровне, приближение монотонно и непрерывно: близкие аргументы дают близкий результат. Точности (менее 0,2 % в меньшую сторону и никогда — в большую) не хватает для настоящих численных расчётов, однако вполне достаточно для трёхмерной графики.
| Property | Value |
|---|---|
| dbo:abstract | Fast inverse square root, sometimes referred to as Fast InvSqrt or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates , the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number in IEEE 754 floating-point format. This operation is used in digital signal processing to normalize a vector, such as scaling it to length 1. For example, computer graphics programs use inverse square roots to compute angles of incidence and reflection for lighting and shading. Predated by similar video game algorithms, this one is best known for its implementation in 1999 in Quake III Arena, a first-person shooter video game heavily based on 3D graphics. The algorithm only started appearing on public forums between 2002 and 2003. Computation of square roots usually depends upon many division operations, which for floating point numbers are computationally expensive. The fast inverse square generates a good approximation with only one division step. The algorithm accepts a 32-bit floating-point number as the input and stores a halved value for later use. Then, treating the bits representing the floating-point number as a 32-bit integer, a logical shift right by one bit is performed and the result subtracted from the number 0x5F3759DF (in decimal notation: 1,597,463,007), which is a floating-point representation of an approximation of . This results in the first approximation of the inverse square root of the input. Treating the bits again as a floating-point number, it runs one iteration of Newton's method, yielding a more precise approximation. The algorithm was often misattributed to John Carmack, but in fact the code is based on an unpublished paper by William Kahan and K.C. Ng circulated in May 1986. The original constant was produced from a collaboration between Cleve Moler and Gregory Walsh, while they worked for Ardent Computing in the late 1980s. With subsequent hardware advancements, especially the x86 SSE instruction rsqrtss, this method is not generally applicable to general purpose computing, though it remains an interesting example both historically and for more limited machines, such as low-cost embedded systems. However, more manufacturers of embedded systems are including trigonometric and other math accelerators such as CORDIC, avoiding the need for such algorithms. (en) La raíz cuadrada inversa rápida, a veces conocida como Fast InvSqrt o por la constante hexadecimal 0x5F3759DF, es un algoritmo que estima , el recíproco (o inverso multiplicativo) de la raíz cuadrada de un número en punto flotante de 32 bits. Esta operación se utiliza en el procesamiento digital de señales para normalizar un vector, es decir, convertirlo en un vector de módulo 1. Por ejemplo, los programas de gráficos por ordenador utilizan las raíces cuadradas inversas para calcular los ángulos de incidencia y reflexión para la iluminación y el sombreado. El algoritmo es más conocido por su implementación en 1999 en el código fuente del videojuego de disparos en primera persona Quake III Arena, que hacía un gran uso de los gráficos en 3D. El algoritmo no empezó a aparecer en foros públicos como Usenet hasta 2002 o 2003. El cálculo de las raíces cuadradas suele depender de muchas operaciones de división, que para los números en coma flotante son computacionalmente costosas. El cuadrado inverso rápido genera una buena aproximación con un solo paso de división. Se han descubierto otros videojuegos anteriores a Quake 3 que utilizan un algoritmo similar, aunque la implementación de Quake sigue siendo el ejemplo más conocido. El algoritmo acepta un número en coma flotante de 32 bits como entrada y almacena un valor dividido a la mitad para su uso posterior. A continuación, tratando los bits que representan el número en punto flotante como un entero de 32 bits, se realiza un desplazamiento lógico a la derecha de un bit y el resultado se resta del número 0x5F3759DF (en notación decimal: 1.597.463.007), que es una representación en punto flotante de una aproximación de . Esto resulta en la primera aproximación de la raíz cuadrada inversa de la entrada. Tratando los bits de nuevo como un número en punto flotante, se ejecuta una iteración del método de Newton, produciendo una aproximación más precisa. El algoritmo se atribuyó originalmente a John Carmack, pero una investigación demostró que el código tenía raíces más profundas tanto en el hardware como en el software de los gráficos por ordenador. Los ajustes y alteraciones pasaron por Silicon Graphics y 3dfx Interactive, y la constante original se derivó de una colaboración entre Cleve Moler y Gregory Walsh, mientras Gregory trabajaba para Ardent Computing a finales de la década de los 80. Walsh y Moler adaptaron su versión a partir de un documento inédito de William Kahan y K.C. Ng difundido en mayo de 1986. Con los posteriores avances en el hardware, especialmente los rsqrtss en instrucciones SSE para x86, este método no es aplicable en general a la informática de propósito general, aunque sigue siendo un ejemplo interesante históricamente, así como para máquinas más limitadas, como los sistemas de bajo coste. Sin embargo, cada vez son más los fabricantes que incluyen aceleradores trigonométricos y otros aceleradores matemáticos como CORDIC, obviando la necesidad de estos algoritmos. (es) La racine carrée inverse rapide (en anglais fast inverse square root, parfois abrégé Fast InvSqrt ou par la constante 0x5f3759df en hexadécimal) est une méthode pour calculer x−½, l'inverse de la racine carrée d'un nombre à virgule flottante à simple précision sur 32 bits. L'algorithme a probablement été développé chez Silicon Graphics au début des années 1990. Il a entre autres été utilisé dans le code source de Quake III Arena, un jeu vidéo sorti en 1999. À l'époque, le principal avantage de cet algorithme était d'éviter d'utiliser des coûteuses opérations à virgules flottantes en préférant des opérations sur entiers. Les racines carrées inverses sont utilisées pour calculer les angles d'incidence et la réflexion pour la lumière et l'ombre en imagerie numérique. L'algorithme prend en entrée des flottants de 32 bits non signés et stocke la moitié de cette valeur pour l'utiliser plus tard. Ensuite, il traite le nombre à virgule flottante comme un entier et lui applique un décalage logique à droite d'un bit et le résultat est soustrait à la valeur « magique » 0x5f3759df. Il s'agit de la première approximation de la racine carrée inverse du nombre passé en entrée. En considérant de nouveau les bits comme un nombre à virgule flottante et en appliquant au nombre la méthode de Newton, on améliore cette approximation. Bien que n'assurant pas la précision la plus fine possible, le résultat final est une approximation de la racine carrée inverse d'un nombre à virgule flottante qui s'exécute quatre fois plus vite qu'une division d'un tel nombre. (fr) 고속 역 제곱근(高速逆-根, fast inverse square root)은 때때로 Fast InvSqrt나 16진수 0x5f3759df라고도 하는, IEEE 754 부동소수점 체계의 32비트 실수에 대한 제곱근의 역수를 계산하기 위한 알고리즘이다. 이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다. 이 알고리즘에 관한 논의가 2000년에 중국어 개발자 포럼 CSDN에서 있었고, 공중에 알려진 것은 2002년 또는 2003년에 유즈넷과 같은 공개 포럼에서였다. 이 알고리즘은 컴퓨터 그래픽스에서 조명과 셰이딩을 위한 입사각과 반사각 계산에 사용되면서 대규모 부동소수점 연산의 계산 비용 문제 해소에 도움이 되었다. 이 알고리즘은 실수를 입력 받아 나중에 사용할 절반의 값을 따로 저장한 다음, 입력 받은 float 실수를 long 비트로 취급한다. 한 비트를 오른쪽 논리 시프트한 결과가 매직 넘버 0x5f3759df에서 감산되며, 더 정확한 근사를 위해 이 근사치를 다시 float 실수로 취급하여 뉴턴의 방법을 한 번 사용한다. 이 알고리즘은 float 실수의 나눗셈을 사용하는 것보다 거의 네 배 더 빠르게 역 제곱근을 계산한다. 존 카맥은 퀘이크 3 아레나에 사용된 소스 코드에 대해 이드 소프트웨어에서 퀘이크의 최적화를 도왔던 탁월한 어셈블리 프로그래머인 Terje Mathisen이 작성했을 것으로 보았다. 그러나 이러한 방법이 하드웨어 개발과 소프트웨어 개발 모두에서 뿌리 깊게 사용되고 있었던 것으로 나타났고, 알려진 최초의 사용으로는 의 SGI Indigo를 위한 구현이 실리콘 그래픽스와 3dfx 인터랙티브를 거쳤다. Rys Sommefeldt는 Ardent Computer의 Greg Walsh가 MATLAB을 설계한 와의 협의를 거쳐 이 알고리즘을 만들었다고 결론지었다. (ko) La radice quadrata inversa veloce (conosciuta in inglese come Fast inverse square root o come Fast InvSqrt o anche dalla costante esadecimale 0x5f3759df) è un metodo per calcolare x−½, ovvero il reciproco (o inverso moltiplicativo) di una radice quadrata per un numero float a 32-bit nel formato "IEEE 754 single precision binary floating-point format: binary32". L'algoritmo è stato probabilmente sviluppato presso la Silicon Graphics all'inizio degli anni '90, l'implementazione apparve nel 1999 all'interno del codice sorgente del gioco Quake III Arena, ma il metodo non è apparso su forum pubblici come Usenet fino al 2002 o al 2003. All'epoca, il vantaggio principale dell'algoritmo proveniva dall'evitare operazioni su float, computazionalmente costose, a favore di operazioni su interi. La radice quadrata inversa è usata per calcolare l'angolo d'incidenza e i riflessi della luce e delle ombre nella computer grafica. L'algoritmo accetta numeri float a 32-bit come input e ne salva il valore dimezzato per usarlo in seguito. Successivamente, trattando i bit che rappresentano il float come un integer a 32-bit, viene effettuato un a destra di un bit e il risultato è poi sottratto dalla "costante magica" 0x5f3759df. Questa è la prima approssimazione della radice quadrata inversa dell'input. Trattando i bit nuovamente come float si esegue una iterazione del Metodo di Newton per ottenere una approssimazione più precisa. Questo calcola una approssimazione della radice quadrata inversa su un float con una velocità approssimativamente 4 volte più veloce della divisione su float. Inizialmente l'algoritmo è stato attribuito a John Carmack, ma successive ricerche hanno mostrato che il codice ha radici più profonde che coinvolgono sia il software che l'hardware usato nella computer grafica. Modifiche ed alterazioni sono state introdotte nel tempo sia dalla Silicon Graphics che dalla 3dfx Interactive, fino ad arrivare al primo utilizzo noto con la implementazione di Gary Tarolli per il SGI Indigo. Non è noto come la costante sia stata derivata originalmente anche se le ricerche hanno portato luce su alcuni possibili metodi di derivazione della stessa. (it) Szybka odwrotność pierwiastka kwadratowego, czasami określana jako szybki InvSqrt lub przez stałą szesnastkową 0x5f3759df – metoda obliczania odwrotności pierwiastka kwadratowego z 32-bitowej liczby zmiennoprzecinkowej w standardzie IEEE 754. Algorytm został prawdopodobnie opracowany w Silicon Graphics na początku lat 90. XX wieku, a jedna z jego implementacji pojawiła się w 1999 roku w kodzie źródłowym gry Quake III: Arena, lecz metoda nie pojawiła się na forach publicznych, takich jak Usenet aż do roku 2002 lub 2003. W ówczesnym czasie podstawowa zaleta algorytmu polegała na unikaniu kosztownych obliczeniowo operacji zmiennoprzecinkowych na korzyść operacji na liczbach całkowitych. Odwrotności pierwiastków kwadratowych są używane do obliczania kątów padania i odbicia dla oświetlenia i cieniowania w grafice komputerowej. Algorytm na wejściu przyjmuje dodatnią 32-bitową liczbę zmiennoprzecinkową i zachowuje jej połowę do późniejszego wykorzystania. Następnie, interpretując bitową reprezentację liczby zmiennoprzecinkowej jako 32-bitową liczbę całkowitą, dokonuje przesunięcia bitowego w prawo o jeden bit, a wynik odejmuje od „magicznej” wartości 0x5f3759df. Jest to pierwsze przybliżenie odwrotności pierwiastka kwadratowego z argumentu. Interpretując ponownie reprezentację bitową jako liczbę zmiennoprzecinkową, stosuje jedną iterację metody Newtona do wyznaczenia dokładniejszego przybliżenia. Ten algorytm oblicza przybliżenie odwrotności pierwiastka kwadratowego z liczby zmiennoprzecinkowej około cztery razy szybciej niż dzielenie zmiennoprzecinkowe. Pierwotnie algorytm ten został przypisany Johnowi Carmackowi, lecz badania wykazały, że ten kod ma głębsze korzenie, zarówno w sprzęcie, jak i po stronie oprogramowania grafiki komputerowej. Korekty i zmiany wprowadziły tak Silicon Graphics, jak i 3dfx Interactive, w tym samym czasie, co najwcześniej znane zastosowanie implementacji Gary’ego Tarolliego dla . Nie wiadomo, jak początkowo została wyznaczona stała, lecz badania rzucają pewne światło na tę kwestię. (pl) 平方根倒数速算法（英語：Fast Inverse Square Root，亦常以“Fast InvSqrt”或其使用的十六进制常数0x5f3759df代称）是用于快速计算（即的平方根的倒数，在此需取符合IEEE 754标准格式的32位浮点数）的一种算法。此算法最早可能是于90年代前期由SGI所发明，后来则于1999年在《雷神之锤III竞技场》的源代码中应用，但直到2002－2003年间才在Usenet一类的公共论坛上出现。这一算法的优势在于减少了求平方根倒数时浮点运算操作带来的巨大的运算耗费，而在计算机图形学领域，若要求取照明和投影的波动角度与反射效果，就常需计算平方根倒数。 此算法首先接收一个32位带符浮点数，然后将之作为一个32位整数看待，以将其向右进行一次逻辑移位的方式将之取半，并用在浮點數規格代表√2127近似值的十六进制“魔术数字”0x5f3759df减之，如此即可得对输入的浮点数的平方根倒数的首次近似值；而后重新将其作为浮点数，以牛顿法反复迭代，以求出更精确的近似值，直至求出符合精确度要求的近似值。在计算浮点数的平方根倒数的同一精度的近似值时，此算法比直接使用浮点数除法要快四倍。 此算法最早被认为是由约翰·卡马克所发明，但后来的调查显示，该算法在这之前就于计算机图形学的硬件与软件领域有所应用，如SGI和3dfx就曾在产品中应用此算法。而就现在所知，此算法最早由加里·塔罗利（Gary Tarolli）在的开发中使用。虽说随后的相关研究也提出了一些可能的来源，但至今为止仍未能确切知晓算法中所使用的特殊常数的起源。 (zh) Швидкий обернений квадратний корінь (іноді згадуваний як Fast InvSqrt або за шістнадцятковою сталою 0x5f3759df) — це метод обчислення , оберненого квадратного кореня для 32-бітного числа у форматі чисел з рухомою комою IEEE 754. Алгоритм ймовірно розробили у Silicon Graphics на початку 1990-х, і реалізація з'явилась 1999 року в сирцевому коді Quake III Arena, але метод не з'являвся на публічних форумах як-от Usenet до 2002 чи 2003. (Існує обговорення на китайському форумі розробників CSDN у 2000.) На той час, основна перевага алгоритму полягала у використанні замість обчислювально дорогих операцій над числами з рухомою комою операцій над цілими числами. Обернений квадратний корінь використовують для обчислення кутів падіння і відбивання для освітлення і шейдинга в комп'ютерній графіці. Алгоритм приймає 32-бітне число з рухомою комою і зберігає його половинне значення для подальшого використання. Тоді, трактуючи числа з рухомою комою як цілі, виконується логічний зсув вправо на один біт і результат віднімається від магічного числа 0x5f3759df. Це буде першим наближенням до оберненого квадратного кореня вхідного числа. Знов трактуючи біти як число з рухомою комою проводиться одна ітерація методу Ньютона, щоб результат був точнішим. Так обчислення наближеного значення оберненого квадратного кореня для числа з рухомою комою відбувається приблизно вчетверо швидше ніж із використанням ділення чисел з рухомою комою. (uk) Бы́стрый обра́тный квадра́тный ко́рень (также быстрый InvSqrt или 0x5F3759DF по используемой «магической» константе, в десятичной системе 1 597 463 007) — это быстрый приближённый алгоритм вычисления обратного квадратного корня для положительных 32-битных чисел с плавающей запятой. Алгоритм использует целочисленные операции «вычесть» и «битовый сдвиг», а также дробные «вычесть» и «умножить» — без медленных операций «разделить» и «квадратный корень». Несмотря на «хакерство» на битовом уровне, приближение монотонно и непрерывно: близкие аргументы дают близкий результат. Точности (менее 0,2 % в меньшую сторону и никогда — в большую) не хватает для настоящих численных расчётов, однако вполне достаточно для трёхмерной графики. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/OpenArena-Rocket.jpg?width=300 |
| dbo:wikiPageExternalLink | https://archive.org/details/computerorganiz000henn http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf http://www.hackszine.com/blog/archive/2008/12/quakes_fast_inverse_square_roo.html http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf https://archive.softwareheritage.org/swh:1:dir:c6f07c2173a458d098de45d4c459a8f1916d900f;origin=https:/github.com/id-Software/Quake-III-Arena;visit=swh:1:snp:4ab9bcef131aaf449a7c01370aff8c91dcecbf5f;anchor=swh:1:rev:dbe4ddb10315479fc00086f08e25d968b4b43c49 https://www.beyond3d.com/content/articles/8/ http://www.gutenberg.org/files/38769 https://github.com/id-Software/Quake-III-Arena https://standards.ieee.org/findstds/standard/754-1985.html https://www.desmos.com/calculator/yoz6n1wlvu http://www.desmos.com https://archive.org/details/isbn_9781558605930 https://link.springer.com/content/pdf/10.1007/978-0-387-72258-0_14.pdf https://web.archive.org/web/20090215020337/http:/www.hackszine.com/blog/archive/2008/12/quakes_fast_inverse_square_roo.html https://web.archive.org/web/20120920120948/http:/blog.quenta.org/2012/09/0x5f3759df.html https://web.archive.org/web/20150511044204/http:/www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf https://web.archive.org/web/20190501235316/https:/link.springer.com/content/pdf/10.1007/978-0-387-72258-0_14.pdf https://www.youtube.com/watch%3Fv=p8u_k2LIZyo |
| dbo:wikiPageID | 20989916 (xsd:integer) |
| dbo:wikiPageLength | 33948 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121981003 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge dbr:Cambridge_University_Press dbr:Quake_III_Arena dbr:Binary_logarithm dbr:Bitwise_operation dbr:Derivative dbr:Approximation_error dbr:Approximation_theory dbr:Uniform_norm dbr:International_Federation_for_Information_Processing dbr:Multiplicative_inverse dbc:Source_code dbr:Single-precision_floating-point_format dbr:Usenet dbr:Cleve_Moler dbr:Table_of_logarithms dbr:Computer_graphics dbr:Computer_graphics_lighting dbr:Halley's_method dbr:CORDIC dbr:C_preprocessor dbr:Transform,_clipping,_and_lighting dbr:Type_conversion dbr:Type_punning dbr:William_Kahan dbr:Lambert's_cosine_law dbr:Logical_shift dbr:Rate_of_convergence dbr:3dfx_Interactive dbr:Activision dbr:Euclidean_norm dbr:Floating-point_arithmetic dbr:Angle_of_incidence_(optics) dbr:Dimension_(vector_space) dbr:Floating-point dbr:Reflection_(computer_graphics) dbr:Hexadecimal dbr:Interstate_'76 dbr:Irvine,_California dbr:Ardent_Computer dbc:Articles_with_example_C_code dbc:Root-finding_algorithms dbr:Jim_Blinn dbr:Trial_and_error dbr:Zero_of_a_function dbr:Digital_signal_processing dbc:Quake_(series) dbr:Square_root dbr:Field-programmable_gate_array dbr:Id_Software dbr:Id_Tech_3 dbr:Institute_of_Electrical_and_Electronics_Engineers dbr:Integer_(computer_science) dbr:Methods_of_computing_square_roots dbr:Newton's_method dbr:O'Reilly_Media dbr:Shading dbr:X86 dbr:YouTube dbr:John_D._Carmack dbr:Unit_vector dbr:Lookup_table dbr:Magic_number_(programming) dbr:Streaming_SIMD_Extensions dbr:Undefined_behavior dbr:Union_type dbr:Exponent_bias dbr:IEEE_754-1985 dbr:First-person_shooter dbr:Normal_number_(computing) dbr:Normalized_number dbr:List_of_Institute_of_Electrical_and_Electronics_Engineers_publications dbr:Vector_components dbr:QuakeCon_2005 dbr:3D_graphics dbr:Vertex_shader dbr:Comment_out dbr:Computationally_expensive dbr:Root-finding_method dbr:File:Float_w_significand_2.svg dbr:File:Log_by_aliasing_to_int.svg dbr:File:OpenArena-Rocket.jpg dbr:File:Reflection_for_Semicircular_Mirror.svg dbr:File:Surface_normals.svg |
| dbp:direction | vertical (en) |
| dbp:footer | Relative error between direct calculation and fast inverse square root carrying out 0, 1, 2, 3, and 4 iterations of Newton's root-finding method. Note that double precision is adopted and the smallest representable difference between two double precision numbers is reached after carrying out 4 iterations. (en) |
| dbp:image | 2 (xsd:integer) 3 (xsd:integer) 4 (xsd:integer) First initial approximate value.png (en) Relative error between Fast inverse square root and 1-sqrt.png (en) |
| dbp:imageGap | 0 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Excessive_detail dbt:Citation dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_web dbt:Good_article dbt:Main dbt:Mono dbt:Multiple_image dbt:Open_access dbt:R dbt:Refbegin dbt:Refend dbt:Reflist dbt:Refn dbt:Sfn dbt:Short_description dbt:Harvid dbt:Format_link dbt:Quake dbt:Id_Software |
| dct:subject | dbc:Source_code dbc:Articles_with_example_C_code dbc:Root-finding_algorithms dbc:Quake_(series) |
| gold:hypernym | dbr:Method |
| rdf:type | dbo:Software yago:WikicatRoot-findingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Бы́стрый обра́тный квадра́тный ко́рень (также быстрый InvSqrt или 0x5F3759DF по используемой «магической» константе, в десятичной системе 1 597 463 007) — это быстрый приближённый алгоритм вычисления обратного квадратного корня для положительных 32-битных чисел с плавающей запятой. Алгоритм использует целочисленные операции «вычесть» и «битовый сдвиг», а также дробные «вычесть» и «умножить» — без медленных операций «разделить» и «квадратный корень». Несмотря на «хакерство» на битовом уровне, приближение монотонно и непрерывно: близкие аргументы дают близкий результат. Точности (менее 0,2 % в меньшую сторону и никогда — в большую) не хватает для настоящих численных расчётов, однако вполне достаточно для трёхмерной графики. (ru) Fast inverse square root, sometimes referred to as Fast InvSqrt or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates , the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number in IEEE 754 floating-point format. This operation is used in digital signal processing to normalize a vector, such as scaling it to length 1. For example, computer graphics programs use inverse square roots to compute angles of incidence and reflection for lighting and shading. Predated by similar video game algorithms, this one is best known for its implementation in 1999 in Quake III Arena, a first-person shooter video game heavily based on 3D graphics. The algorithm only started appearing on public forums between 2002 and 2003. Computation of square ro (en) La raíz cuadrada inversa rápida, a veces conocida como Fast InvSqrt o por la constante hexadecimal 0x5F3759DF, es un algoritmo que estima , el recíproco (o inverso multiplicativo) de la raíz cuadrada de un número en punto flotante de 32 bits. Esta operación se utiliza en el procesamiento digital de señales para normalizar un vector, es decir, convertirlo en un vector de módulo 1. Por ejemplo, los programas de gráficos por ordenador utilizan las raíces cuadradas inversas para calcular los ángulos de incidencia y reflexión para la iluminación y el sombreado. El algoritmo es más conocido por su implementación en 1999 en el código fuente del videojuego de disparos en primera persona Quake III Arena, que hacía un gran uso de los gráficos en 3D. El algoritmo no empezó a aparecer en foros públ (es) La racine carrée inverse rapide (en anglais fast inverse square root, parfois abrégé Fast InvSqrt ou par la constante 0x5f3759df en hexadécimal) est une méthode pour calculer x−½, l'inverse de la racine carrée d'un nombre à virgule flottante à simple précision sur 32 bits. L'algorithme a probablement été développé chez Silicon Graphics au début des années 1990. Il a entre autres été utilisé dans le code source de Quake III Arena, un jeu vidéo sorti en 1999. À l'époque, le principal avantage de cet algorithme était d'éviter d'utiliser des coûteuses opérations à virgules flottantes en préférant des opérations sur entiers. Les racines carrées inverses sont utilisées pour calculer les angles d'incidence et la réflexion pour la lumière et l'ombre en imagerie numérique. (fr) La radice quadrata inversa veloce (conosciuta in inglese come Fast inverse square root o come Fast InvSqrt o anche dalla costante esadecimale 0x5f3759df) è un metodo per calcolare x−½, ovvero il reciproco (o inverso moltiplicativo) di una radice quadrata per un numero float a 32-bit nel formato "IEEE 754 single precision binary floating-point format: binary32". L'algoritmo è stato probabilmente sviluppato presso la Silicon Graphics all'inizio degli anni '90, l'implementazione apparve nel 1999 all'interno del codice sorgente del gioco Quake III Arena, ma il metodo non è apparso su forum pubblici come Usenet fino al 2002 o al 2003. All'epoca, il vantaggio principale dell'algoritmo proveniva dall'evitare operazioni su float, computazionalmente costose, a favore di operazioni su interi. La r (it) 고속 역 제곱근(高速逆-根, fast inverse square root)은 때때로 Fast InvSqrt나 16진수 0x5f3759df라고도 하는, IEEE 754 부동소수점 체계의 32비트 실수에 대한 제곱근의 역수를 계산하기 위한 알고리즘이다. 이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다. 이 알고리즘에 관한 논의가 2000년에 중국어 개발자 포럼 CSDN에서 있었고, 공중에 알려진 것은 2002년 또는 2003년에 유즈넷과 같은 공개 포럼에서였다. 이 알고리즘은 컴퓨터 그래픽스에서 조명과 셰이딩을 위한 입사각과 반사각 계산에 사용되면서 대규모 부동소수점 연산의 계산 비용 문제 해소에 도움이 되었다. (ko) Szybka odwrotność pierwiastka kwadratowego, czasami określana jako szybki InvSqrt lub przez stałą szesnastkową 0x5f3759df – metoda obliczania odwrotności pierwiastka kwadratowego z 32-bitowej liczby zmiennoprzecinkowej w standardzie IEEE 754. Algorytm został prawdopodobnie opracowany w Silicon Graphics na początku lat 90. XX wieku, a jedna z jego implementacji pojawiła się w 1999 roku w kodzie źródłowym gry Quake III: Arena, lecz metoda nie pojawiła się na forach publicznych, takich jak Usenet aż do roku 2002 lub 2003. W ówczesnym czasie podstawowa zaleta algorytmu polegała na unikaniu kosztownych obliczeniowo operacji zmiennoprzecinkowych na korzyść operacji na liczbach całkowitych. Odwrotności pierwiastków kwadratowych są używane do obliczania kątów padania i odbicia dla oświetlenia i (pl) Швидкий обернений квадратний корінь (іноді згадуваний як Fast InvSqrt або за шістнадцятковою сталою 0x5f3759df) — це метод обчислення , оберненого квадратного кореня для 32-бітного числа у форматі чисел з рухомою комою IEEE 754. Алгоритм ймовірно розробили у Silicon Graphics на початку 1990-х, і реалізація з'явилась 1999 року в сирцевому коді Quake III Arena, але метод не з'являвся на публічних форумах як-от Usenet до 2002 чи 2003. (Існує обговорення на китайському форумі розробників CSDN у 2000.) На той час, основна перевага алгоритму полягала у використанні замість обчислювально дорогих операцій над числами з рухомою комою операцій над цілими числами. Обернений квадратний корінь використовують для обчислення кутів падіння і відбивання для освітлення і шейдинга в комп'ютерній графіці. (uk) 平方根倒数速算法（英語：Fast Inverse Square Root，亦常以“Fast InvSqrt”或其使用的十六进制常数0x5f3759df代称）是用于快速计算（即的平方根的倒数，在此需取符合IEEE 754标准格式的32位浮点数）的一种算法。此算法最早可能是于90年代前期由SGI所发明，后来则于1999年在《雷神之锤III竞技场》的源代码中应用，但直到2002－2003年间才在Usenet一类的公共论坛上出现。这一算法的优势在于减少了求平方根倒数时浮点运算操作带来的巨大的运算耗费，而在计算机图形学领域，若要求取照明和投影的波动角度与反射效果，就常需计算平方根倒数。 此算法首先接收一个32位带符浮点数，然后将之作为一个32位整数看待，以将其向右进行一次逻辑移位的方式将之取半，并用在浮點數規格代表√2127近似值的十六进制“魔术数字”0x5f3759df减之，如此即可得对输入的浮点数的平方根倒数的首次近似值；而后重新将其作为浮点数，以牛顿法反复迭代，以求出更精确的近似值，直至求出符合精确度要求的近似值。在计算浮点数的平方根倒数的同一精度的近似值时，此算法比直接使用浮点数除法要快四倍。 (zh) |
| rdfs:label | Algoritmo de la raíz cuadrada inversa rápida (es) Fast inverse square root (en) Racine carrée inverse rapide (fr) Radice quadrata inversa veloce (it) 고속 역 제곱근 (ko) Szybka odwrotność pierwiastka kwadratowego (pl) Быстрый обратный квадратный корень (ru) Швидкий обернений квадратний корінь (uk) 平方根倒数速算法 (zh) |
| owl:sameAs | freebase:Fast inverse square root yago-res:Fast inverse square root wikidata:Fast inverse square root http://bn.dbpedia.org/resource/দ্রুত_বিপরীত_বর্গমূল dbpedia-es:Fast inverse square root dbpedia-fr:Fast inverse square root dbpedia-it:Fast inverse square root dbpedia-ko:Fast inverse square root dbpedia-pl:Fast inverse square root dbpedia-ru:Fast inverse square root dbpedia-sr:Fast inverse square root dbpedia-uk:Fast inverse square root dbpedia-zh:Fast inverse square root https://global.dbpedia.org/id/32cJH |
| prov:wasDerivedFrom | wikipedia-en:Fast_inverse_square_root?oldid=1121981003&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/2nd-iter.png wiki-commons:Special:FilePath/3rd-iter.png wiki-commons:Special:FilePath/4th-iter.png wiki-commons:Special:FilePath/First_initial_approximate_value.png wiki-commons:Special:FilePath/Float_w_significand_2.svg wiki-commons:Special:FilePath/Log_by_aliasing_to_int.svg wiki-commons:Special:FilePath/Reflection_for_Semicircular_Mirror.svg wiki-commons:Special:FilePath/Relative_error_betwee..._inverse_square_root_and_1-sqrt().png wiki-commons:Special:FilePath/Surface_normals.svg wiki-commons:Special:FilePath/OpenArena-Rocket.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Fast_inverse_square_root |
| is dbo:wikiPageRedirects of | dbr:/_what_the_fuck? dbr:0x5f3759df dbr:5F3759DF dbr:5f375a86 dbr:Fast_InvSqrt() dbr:Fast_square_root dbr:Q_rsqrt dbr:1597463174 dbr:0x5F3759DF dbr:0x5f375a86 dbr:Carmack's_number |
| is dbo:wikiPageWikiLink of | dbr:Undefined_value dbr:List_of_numerical_analysis_topics dbr:/_what_the_fuck? dbr:0x5f3759df dbr:Single-precision_floating-point_format dbr:Type_punning dbr:OpenAI_Codex dbr:Strength_reduction dbr:John_Carmack dbr:Id_Tech_3 dbr:Newton's_method dbr:Magic_number_(programming) dbr:5F3759DF dbr:5f375a86 dbr:Fast_InvSqrt() dbr:Fast_square_root dbr:Q_rsqrt dbr:1597463174 dbr:0x5F3759DF dbr:0x5f375a86 dbr:Carmack's_number |
| is foaf:primaryTopic of | wikipedia-en:Fast_inverse_square_root |
