number 0x5f3759df 0 - 100 - 01001110101100111011 = 1. 307430... * 2 ^ 1, The result of 0x5f3759df - ( i > > 1 ) 이 결과는 2. 61486으로 약 3. 4 % 의 오차를 갖는다. 뉴턴의 방법을 한 번 사용하면 2. 52549로 약 0. 17 % 의 오차를 갖게 된다. 알고리즘 설명 [ 편집 ] 이 알고리즘은 다음 단계들을 수행해서 x - 1 / 2 { displaystyle x ^ { - 1 / 2 } } 를 계산한다 : float 양수 x { displaystyle x } 를 long 비트로 취급하면 log 2 ( x ) { displaystyle log - { 2 } ( x ) } 로 다룰 수 있다. 매직 넘버를 사용하여 - log 2 ( x ) / 2 { displaystyle - log - { 2 } ( x ) / 2 } 의 근사치를 계산한다. long 비트 log 2 ( x - 1 / 2 ) { displaystyle log - { 2 } ( x ^ { - 1 / 2 } ) } 를 다시 float 양수로 취급하면 x - 1 / 2 { displaystyle x ^
left ( { frac { 3 } { 2 } } - { frac { x } { 2 } } ( y - { 0 } ) ( y - { 0 } ) ^ { 2 } right ) } 으로 방정식 f ( x - 1 / 2 ) = 0 { displaystyle f ( x ^ { - 1 / 2 } ) = 0 } 의 해인 역 제곱근을 근사할 수 있다. 이것은 다음 코드로 쓰였다 : y = y * ( threehalfs - ( x2 * y * y ) ( x2 * y * y ) ) ; / / 1st iteration 정확도 [ 편집 ] libstdc의 역 제곱근과 휴리스틱적인 고속 역 제곱근의 차이. 오른쪽 그래프는 뉴턴의 방법을 한 번 사용하여 개선된 오차를 보여 준다. 0. 01에 대해 표준 라이브러리는 10. 0을, 위 알고리즘을 적용한 함수는 9. 982522를 반환하며, 로그 스케일에서 서로의 차이는 일정한 영역을 벗어나지 않는다. Chris Lomont는 더 정확하게 근사하는 매직 넘버 0x5f375a86을, Matthew Robertson은 배정도 표현에서 유효한 매직 넘버 0x5fe6eb50c7b537a9를 찾아냈다. [ 6 ] 각주 [ 편집 ] ↑
##는 그 의미를 즉시 파악하기 어렵기 때문에 이 알고리즘의 매직 넘버라고 불린다. 이 알고리즘은 뉴턴의 방법을 사용하여 비교적 정확한 결과를 만들어 내지만, 소수점의 손실 때문에 부정확하고 1999년부터 도입된 x86 SSE의 rsqrtss에 비해 훨씬 느리다. [ 5 ] 또한 long을 사용하는 것은 64비트 시스템에 대한 코드의 이식성을 떨어뜨릴 수 있다. 실행 예시 [ 편집 ] 다음은 x = 0. 15625 { displaystyle x = 0. 15625 } 에 대해 x - 1 / 2 2. 52982 { displaystyle x ^ { - 1 / 2 } approx 2. 52982 } 를 근사하는 과정이다 : 0 - 01100 - 0100 = 1. 25 * 2 ^ - 3, Bit pattern of both x and i 0 - 00110 - 00100 = 1. 125 * 2 ^ - 65, Shift right one position : ( i > > 1 ) 0 - 10110 - 01101110101100111011 = 1. 432430... * 2 ^ 63, The magic number 0x5f3759df 0 - 100 - 01001110101100111011 = 1. 3074
##는 그 절반인 = 0. 0430357 { displaystyle sigma = 0. 0430357 } 이다. float 양수에 대한 로그 근사 ( 파란색 ) 와 로그 함수 ( 회색 ). 한편 양수 x { displaystyle x } 를 비트 n x { displaystyle n - { x } } 로 취급하면 n x = 2 23 ( E 127 ) 2 23 x M = 2 23 ( E M ) 2 23 ( 127 - ) 2 23 log 2 ( x ) 2 23 ( 127 - ) { displaystyle { begin { aligned } n - { x } & = 2 ^ { 23 } ( mathrm { E } 127 ) 2 ^ { 23 } times mathrm { M } & = 2 ^ { 23 } ( mathrm { E } sigma mathrm { M } ) 2 ^ { 23 } ( 127 - sigma ) & approx 2 ^ { 23 } log - { 2 } ( x ) 2 ^ { 23 } ( 127 - sigma ) end { aligned } } } 이다. = 0. 0430357 { displaystyle sigma = 0. 0430
고속 역 제곱근 - 위키백과, 우리 모두의 백과사전 고속 역 제곱근 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 위 사진에 나타난 1인칭 슈팅 게임 OpenArena의 조명 처리와 같은 연산에 입사각과 반사각을 계산할 때 고속 역 제곱근 알고리즘을 사용한다. 고속 역 제곱근 ( 高 -, fast inverse square root ) 은 때때로 Fast InvSqrt나 16진수 0x5f3759df라고도 하는, IEEE 754 부동 소수점 체계의 32비트 실수에 대한 제곱근의 역수를 계산하기 위한 알고리즘이다. 이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다. 이 알고리즘에 관한 논의가 2000년에 중국어 개발자 포럼 CSDN에서 있었고, [ 1 ] 공중에 알려진 것은 2002년 또는 2003년에 유즈넷과 같은 공개 포럼에서였다. [ 2 ] 이 알고리즘은 컴퓨터 그래픽스에서 조명과 셰이딩을 위한 입사각과 반사각 계산에 사용되면서 대규모 부동 소수점 연산의 계산 비용 문제 해소에 도움이 되었다. 이 알고리즘은 실수를 입력 받아 나중에 사용할 절반의
{ 3 } ^ { 2 } } } } right ) } 여기서 실수 x { displaystyle x } 에 대한 역 제곱근 1 x { displaystyle { frac { 1 } { sqrt { x } } } } 이 등장한다. 3차원 컴퓨터 그래픽스에서는 이러한 연산을 매초 수백만 번 수행해야 했고, 이것은 특수한 하드웨어가 출현하기 전까지 번거로운 작업이었다. 1990년대 초에는 실수의 처리 능력이 정수 처리에 비해서 뒤처져 있었으나, 고속 역 제곱근 알고리즘은 float 실수의 우회하여 이러한 문제 해소에 도움이 되었다. 퀘이크 3 아레나에서 그래픽 연산 속도를 개선하기 위해서 사용되었고, 이후 FPGA를 사용하는 일부 특수한 하드웨어 버텍스 셰이더에 구현되기도 했다. 코드 [ 편집 ] 다음 코드는 퀘이크 3 아레나에 사용된 것으로, C 전처리 지시문을 생략했지만 본래의 정확한 주석까지 포함하였다. [ 4 ] float Q - rsqrt ( float number ) { long i ; float x2, y ; const float threehalfs = 1. 5F ; x2 = number * 0. 5F ; y = number ;
##규모 부동 소수점 연산의 계산 비용 문제 해소에 도움이 되었다. 이 알고리즘은 실수를 입력 받아 나중에 사용할 절반의 값을 따로 저장한 다음, 입력 받은 float 실수를 long 비트로 취급한다. 한 비트를 오른쪽 논리 시프트한 결과가 매직 넘버 0x5f3759df에서 감산되며, 더 정확한 근사를 위해 이 근사치를 다시 float 실수로 취급하여 뉴턴의 방법을 한 번 사용한다. 이 알고리즘은 float 실수의 사용하는 것보다 거의 네 배 더 빠르게 역 제곱근을 계산한다. 존 카맥은 퀘이크 3 아레나에 사용된 소스 코드에 대해 이드 소프트웨어에서 퀘이크의 최적화를 도왔던 탁월한 어셈블리 프로그래머인 Terje Mathisen이 작성했을 것으로 보았다. 그러나 이러한 방법이 하드웨어 개발과 소프트웨어 개발 모두에서 뿌리 깊게 사용되고 있었던 것으로 나타났고, 알려진 최초의 사용으로는 게리 타롤리의 SGI Indigo를 위한 구현이 실리콘 그래픽스와 3dfx 인터랙티브를 거쳤다. Rys Sommefeldt는 Ardent Computer의 Greg Walsh가 MATLAB을 설계한 클리브 몰러와의 협의를 거쳐 이 알고리즘을 만들었다고 결론지었다. [ 3 ] 목차
매직 넘버 0x5fe6eb50c7b537a9를 찾아냈다. [ 6 ] 각주 [ 편집 ] ↑ " Discussion on CSDN ". 2015년 7월 2일에 원본 문서에서 보존된 문서. ↑ Sommefeldt, Rys ( 2006년 11월 29일 ). " Origin of Quake3's Fast InvSqrt ". 《 Beyond3D 》. 2009년 2월 12일에 확인함. ↑ Sommefeldt, Rys ( 2006년 12월 19일 ). " Origin of Quake3's Fast InvSqrt - Part Two ". Beyond3D. 2008년 4월 19일에 확인함. ↑ " quake3 - 1. 32b / code / game / q - math. c ". 《 Quake III Arena 》. id Software. 2017년 1월 21일에 확인함. ↑ Ruskin, Elan ( 2009년 10월 16일 ). " Timing square root ". 《 Some Assembly Required 》. 2015년 5월 7일에 확인함. ↑ Matthew Robertson ( 2012년 4월 24일 ). " A Brief History of In
0 leq mathrm { M } < 1 } 를 고려하여 log 2 ( 1 M ) M { displaystyle log - { 2 } ( 1 mathrm { M } ) approx sigma mathrm { M } } 로 근사할 수 있는 상수 { displaystyle sigma } 를 사용한다. ( log 2 ( 1 M ) ( 1 M ) - M ) = 1 M ln 2 ln 2 - 1 { displaystyle ( log - { 2 } ( 1 mathrm { M } ) ( 1 mathrm { M } ) - mathrm { M } )'= { frac { 1 } { mathrm { M } ln 2 ln 2 } } - 1 } 이고 극댓값은 M = 1 ln 2 - 1 { displaystyle mathrm { M } = { frac { 1 } { ln 2 } } - 1 } 에서 0. 0860713이기 때문에, 오차의 최댓값이 가장 작은 상수는 그 절반인 = 0. 0430357 { displaystyle sigma = 0. 0430357
Christian Plesner Hansen Origin of Quake3's Fast InvSqrt Quake III Arena source code Margolin, Tomer ( 2005년 8월 27일 ). " Magical Square Root Implementation In Quake III ". 《 CodeMaestro 》. The Coding Experience. 2012년 4월 14일에 원본 문서에서 보존된 문서. 2012년 5월 15일에 확인함. 원본 주소 " " 분류 : 소스 코드수치해석학퀘이크 시리즈근 찾기 알고리즘 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 / 中 文 링크 편집 이 문서는 2019년 4월 9일 ( 화 ) 01 : 58에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락
고속 역 제곱근(高速逆-根, 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을 설계한 클리브 몰러와의 협의를 거쳐 이 알고리즘을 만들었다고 결론지었다.