John Carmack은 Quake III 소스 코드 (float)(1.0/sqrt(x))에서 이상한 0x5f3759df상수를 포함하여 regular보다 4 배 빠른 float의 역 제곱근을 계산하는 특수 함수를 가지고 있습니다. 아래 코드를 참조하십시오. 누군가 여기서 정확히 무슨 일이 일어나고 있으며 왜 이것이 일반 구현보다 훨씬 빠르게 작동하는지 한 줄씩 설명 할 수 있습니까?
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) );
#endif
#endif
return y;
}답변
참고로. Carmack은 그것을 쓰지 않았습니다. Terje Mathisen과 Gary Tarolli는 둘 다 부분적으로 (그리고 매우 겸손한) 다른 출처를 인정합니다.
신화 상수가 어떻게 파생되었는지는 미스테리입니다.
Gary Tarolli를 인용하려면 :
실제로 정수로 부동 소수점 계산을 수행하고 있습니다. 이것이 작동하는 방법과 이유를 파악하는 데 오랜 시간이 걸렸고 더 이상 세부 사항을 기억할 수 없습니다.
원래 알고리즘이 어떻게 작동하는지 알아 내려는 전문 수학자 (Chris Lomont)가 개발 한 약간 더 나은 상수 는 다음과 같습니다.
float InvSqrt(float x)
{
float xhalf = 0.5f * x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f375a86 - (i >> 1); // gives initial guess y0
x = *(float*)&i; // convert bits back to float
x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
return x;
}
그럼에도 불구하고, 그의 초기 시도는 수학적으로 훨씬 더 순수 했음에도 불구하고 처음에 Gary가 개발 한 것보다 열등한 것으로 증명되었습니다. 그는 이드가 왜 그렇게 훌륭한 iirc인지 설명 할 수 없었다.
답변
물론 요즘에는 FPU의 sqrt (특히 360 / PS3에서)를 사용하는 것보다 훨씬 느린 것으로 밝혀졌습니다. 왜냐하면 float 레지스터와 int 레지스터 사이의 스왑은로드 적중 저장을 유도하는 반면 부동 소수점 단위는 역 제곱을 할 수 있기 때문입니다. 하드웨어의 루트.
기본 하드웨어의 특성이 변경됨에 따라 최적화가 어떻게 발전해야하는지 보여줍니다.
답변
Greg Hewgill 과 IllidanS4 는 훌륭한 수학적 설명과 함께 링크를 제공했습니다. 세부 사항에 너무 많이 들어가고 싶지 않은 사람들을 위해 여기에 요약하려고합니다.
몇 가지 예외를 제외하고 모든 수학 함수는 다항식 합계로 나타낼 수 있습니다.
y = f(x)
정확히 다음과 같이 변환 할 수 있습니다 .
y = a0 + a1*x + a2*(x^2) + a3*(x^3) + a4*(x^4) + ...
여기서 a0, a1, a2, …는 상수 입니다. 문제는 제곱근과 같은 많은 함수의 경우 정확한 값에 대해이 합계는 무한한 수의 구성원을 가지며 일부 x ^ n 에서 끝나지 않는다는 것 입니다. 그러나 만약 우리가 어떤 x ^ n 에서 멈 추면 우리는 여전히 정확도까지의 결과를 가질 것입니다.
따라서 다음과 같은 경우 :
y = 1/sqrt(x)
이 특별한 경우에는 아마도 계산 속도 때문에 모든 다항식 멤버를 두 번째 이상으로 버리기로 결정했습니다.
y = a0 + a1*x + [...discarded...]
그리고 작업은 이제 y가 정확한 값과 가장 작은 차이를 갖도록 a0과 a1을 계산하기 위해 내려 왔습니다. 그들은 가장 적절한 값이 다음과 같다고 계산했습니다.
a0 = 0x5f375a86
a1 = -0.5
따라서 이것을 방정식에 넣으면 다음과 같은 결과를 얻을 수 있습니다.
y = 0x5f375a86 - 0.5*x
코드에 표시되는 줄과 동일합니다.
i = 0x5f375a86 - (i >> 1);
편집 : 실제로 정수로 부동 소수점을 2로 나눌뿐만 아니라 지수를 2로 나누고 다른 아티팩트를 발생 y = 0x5f375a86 - 0.5*x시키기 i = 0x5f375a86 - (i >> 1);때문에 실제로 는 동일 하지 않지만 여전히 일부 계수 a0, a1, a2 ….
이 시점에서 그들은이 결과의 정밀도가 목적에 충분하지 않다는 것을 발견했습니다. 따라서 그들은 결과 정확도를 향상시키기 위해 Newton의 반복의 한 단계 만 수행했습니다.
x = x * (1.5f - xhalf * x * x)
그들은 필요한 정확도가 충족 될 때까지 결과를 개선하는 루프에서 더 많은 반복을 수행 할 수있었습니다. 이것이 바로 CPU / FPU에서 작동하는 방식입니다! 그러나 한 번의 반복만으로도 충분 해 보이며 속도에도 축복이었습니다. CPU / FPU는 결과가 저장되는 부동 소수점 숫자의 정확도에 도달하기 위해 필요한만큼 반복을 수행하며 모든 경우에 작동하는보다 일반적인 알고리즘을 가지고 있습니다.
즉, 그들이 한 일은 다음과 같습니다.
CPU / FPU와 (거의) 동일한 알고리즘을 사용하고, 1 / sqrt (x)의 특수한 경우에 대한 초기 조건의 개선을 이용하고 CPU / FPU가 더 빨리 중지 될 것이므로 정밀하게 계산하지 마십시오. 계산 속도가 증가합니다.
답변
얼마 전에 쓴 이 멋진 기사 에 따르면 …
코드의 마법은 따라갈 수 없더라도 i = 0x5f3759df-(i >> 1); 선. 단순화 된 Newton-Raphson은 추측으로 시작하여 반복으로 구체화하는 근사값입니다. 32 비트 x86 프로세서의 특성을 활용하여 정수인 i는 처음에 정수 캐스트를 사용하여 역 제곱을 취하려는 부동 소수점 숫자 값으로 설정됩니다. i는 0x5f3759df로 설정되고 마이너스 자체가 오른쪽으로 1 비트 이동됩니다. 오른쪽 시프트는 i의 최하위 비트를 떨어 뜨려 본질적으로 절반을 줄입니다.
정말 좋은 읽기입니다. 이것은 단지 작은 조각 일뿐입니다.
답변
상수가 부동 소수점으로 무엇인지 궁금해서이 코드를 작성하고 튀어 나온 정수를 검색했습니다.
long i = 0x5F3759DF;
float* fp = (float*)&i;
printf("(2^127)^(1/2) = %f\n", *fp);
//Output
//(2^127)^(1/2) = 13211836172961054720.000000
상수는 “부동 소수점 표현의 16 진수 형식으로 더 잘 알려진 2 ^ 127의 제곱근에 대한 정수 근사치, 0x5f3759df” https://mrob.com/pub/math/numbers-18.html 처럼 보입니다.
같은 사이트에서 모든 것을 설명합니다. https://mrob.com/pub/math/numbers-16.html#le009_16
답변
