수학주의) 프로그래밍 배운 사람들이 보고 뒤집어진 코드

ㅊㅊ - https://bbs.ruliweb.com/community/board/300143/read/51063314

 

 

원본출처 | https://www.youtube.com/watch?v=p8u_k2LIZyo&t=1035s

 

이것이 뭐냐하면 퀘이크 3 소스코드에 있는 함수다

 

정확히는를 계산하는 함수인데, 광원 효과에 쓰이는 함수라서 굉장히 빨라야 한다

(빛의 반사 계산하는 데 쓰는데, 단위벡터가 어쩌구 반사벡터가 저쩌구 하는 건 생략)

 

중요한 건 느리면 60 프레임을 못맞추고, 빨라도 값의 정확하지 않으면 빛이 이상하게 표현된다

 

나눗셈이랑 제곱근을 쓰는 방법은 정확한 대신 리소스도 많이 필요하고 줜나 느려서 60프레임을 못맞춘다

 

그래서 퀘이크 3 개발진은 저런 함수를 만들어를 빠르고 정확하게 계산했다

 

 

일단 보면 주석에 왓더뻑이라고 적힌 것처럼 씨1발 이게 뭐야 어캐 하는건데 싶어진다

 

그래도 하나 하나 뜯어보면 이해가 되긴 된다

 

우선 맨 앞에 변수의 자료형 두 개가 나온다

 

 

long은 숫자를 이진법으로 00000000 00000000 00000000 00000000으로 표시한다

 

long형에서 특별히 봐야할 건 없으니 넘어가자

 

 

float은 소숫점을 포함한 실수를 0 00000000 00000000000000000000000으로 표현한다

 

첫 자리는 부호를 나타낸다

0이면 양수 또는 0, 1이면 음수를 뜻한다

 

뒤의 8자리는 지수(2^E)를 나타낸다

E = -127를 00000000으로 하고 E = +128을 11111111로 사용한다

 

마지막 23자리는 가수부(M)를 나타낸다

이진법으로 1.00000000000000000000000부터 1.11111111111111111111111까지 소숫점을 나타내는 데 사용한다

 

 

float형을 수식으로 표현하면 이런 꼴이 된다

 

저 수식을 2의 로그로 감싸고 정리하면 

뜬금없이 나온 뮤(μ)는 log2의 근사값을 구하는 데 쓰인 숫자다

 

1보다 작은 x에 대해 ​​​​​​​인데 적당한 수를 더하면(​​​​​​​)전반적인 정확도를 높일 수 있다

 

실험적으로 찾아낸 적절한 값은 μ≒0.0430357이다

참고: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Aliasing_to_an_integer_as_an_approximate_logarithm

 

 

그런데 float형의 비트값은 E*2²³ + M 꼴의 형태가 되는 것을 알고 있다

(여기서 음수는 생각하지 않는다)

 

앞에서 구한 로그값이랑 비교하여 생각해보면 float형의 비트값을 그대로 하나의 정수로 생각하면 이 정수는 원래 값에 log2를 취한 것과 같다고 생각할 수 있다

 

변수 정의 뒤에 나오는 i = * ( long * ) &y; 가 바로 float형으로 받은 비트값을 그대로 숫자로 받는 줄인 것이다

 

 

어찌저찌하여 중간까지는 왔는데 그 다음 줄이 문제다

 

앞서 였고 ​​​​​​​를 구해야 하는데, 로그의 특성에 따라 가 된다!

 

그리고 이진수에서 오른쪽으로 비트를 이동(bit shift)하면 2로 나눈 것과 같은 효과를 얻는다

 

예를 들어 110(10진법으로 6)을 오른쪽으로 비트 이동시키면 11(10진법으로 3)이 된다

 

111(10진법으로 7)도 11(10진법으로 3)이 되는 문제가 있지만 어쩔 수 없이 받아들여야 한다

 

 

오른쪽으로 비트 이동이 >>니까 -0.5i는 -(i >> 1)이 된다

 

그러면 저 0x5f3759df(=1597463040)는 대체 뭔 수일까?

 

 

실제로 구해야 하는 해​​​​​​​​​​​​​​를 감마(Γ)라고 하면 i와 Γ의 관계는 다음과 같다

 

 

이걸 좀전에 봤던 ​​​​​​​꼴로 표현하면,

 

 

정리하면,

 

값을 계산하면, 3/2 * 2²³ * (127-μ) = 1597488309.57 ≒1597463040 = 0x5f3759df

 

그렇다, 오차를 보정하는 값이 바로 저 0x5f3759df였던 거다!

 

 

값을 다 구했으니 구한 값을 float형으로 되돌리고 → y = * (float *) &i;

 

f(x) = 0을 정확하게 구할 때 쓰는 뉴턴-랩슨법을 이용해 정확도를 높여주면 → y = y * (threehalfs - (x2 * y * y));

 

 

그리하여 나눗셈도, 제곱근 계산도 없이 포인트 참조, 비트 이동, 뺄셈, 그리고 곱하기만 가지고 빠르고 비교적 정확하게​​​​​​​를 구할 수 있었다!