빠른 역 제곱근

빠른 역 제곱근은 32 비트 부동 소수점 숫자의 제곱근의 역수(또는 곱셈 역수)를 추정하는 알고리즘입니다. 상호 제곱근을 계산하는 것은 비디오 게임의 벡터 정규화와 같은 많은 응용 프로그램에서 필요하며 주로 3 차원 프로그래밍에 관련된 계산에 사용됩니다. 에 3 차원 그래픽,표면 법선,길이 1 의 3 좌표 벡터가 사용되어 조명과 반사를 표현합니다. 표면 법선이 많이 있었다. 그리고 그것들을 계산하는 것은 많은 벡터를 정규화하는 것을 포함합니다. 정규화는 종종 분할에 대한 멋진 용어입니다. 피타고라스 정리는 점 사이의 거리를 계산하고 거리로 나누면 벡터를 정규화하는 데 도움이됩니다:

이 알고리즘은 1999 년 소스 코드로 구현 된 것으로 가장 잘 알려져 있습니다. 그 당시에는 부동 소수점 숫자의 역수를 계산하는 데 일반적으로 계산 비용이 많이 들었습니다.; 빠른 역 제곱근 이 단계를 우회했습니다.

알고리즘:
1 단계:부동 소수점 입력의 비트를 정수로 재 해석합니다.

i = * ( long * ) &y; 

2 단계:결과 값을 취하고 정수 연산을 수행하여 우리가 찾고있는 값의 근사치를 생성합니다.

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

3 단계:결과는 근사 자체가 아니지만 비트를 부동 소수점 숫자로 재 해석하면 근사 인 정수입니다. 그래서 코드는 부동 소수점으로 돌아 가기 위해 1 단계에서 변환의 반대를 수행합니다:

y = * ( float * ) &i;

4 단계:그리고 마지막으로 근사를 개선하기 위해 뉴턴의 방법의 단일 반복을 실행합니다.

y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;

알고리즘은 32 비트 부동 소수점 숫자를 입력으로 받아들이고 나중에 사용할 수 있도록 절반 값을 저장합니다. 그런 다음 부동 소수점 숫자를 나타내는 비트를 32 비트 정수로 처리하면 1 비트의 논리적 이동이 수행되고 그 결과는 매직 넘버에서 뺍니다. 이 입력의 역 제곱근의 첫 번째 근사치입니다. 부동 소수점 숫자로 다시 비트를 처리,그것은 더 정확한 근사치를 산출,뉴턴의 근사 방법의 한 반복을 실행합니다.

지수 형식 또는 과학적 표기법에 숫자가 있다고 가정 해 봅시다.:
=100 백만
이제 정규 제곱근을 찾기 위해 지수를 2:

그리고 역제곱근을 알고 싶다면 지수를-2 로 나누어 부호를 뒤집습니다:7437>

따라서 코드는 부동 소수점 숫자를 정수로 변환합니다. 그런 다음 비트를 1 씩 이동시킵니다.이 지수 비트는 2 로 나누어집니다(결국 비트를 다시 플로트로 바꿀 때). 그리고 마지막으로 지수를 부정하기 위해 매직 넘버에서 뺍니다. 이것은 몇 가지 작업을 수행합니다:그것은 가수(비 지수 부분,일명 5)를 보존합니다: 5 · ), 홀수-짝수 지수,지수에서 가수로 비트 이동 및 모든 종류의 펑키 한 물건을 처리합니다.

다음 코드는 퀘이크 3 아레나(퀘이크 3 아레나 게임에서 작성된 정확한 원래 주석)에서 빠른 역 제곱근 구현입니다.

출력: