[유머] 프로그래머들 떡실신 시켰다는 전설의 코드

[🐣RED O]

이것이 뭐냐하면 퀘이크 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));

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

출처 : https://bbs.ruliweb.com/etcs/board/300781/read/58465123

[rm -rf]

[루리웹-7448647357-뉴비]

음. 고대언어로 쓰인 미법진이군.

[불량닉네임은 계정징계조치]

더 충격적인건 요즘은 더 효율좋은 알고리즘을 쓰고잇음

[루에이-91123]

요즘은 그냥 FPU가 더 빠르다..
그냥 표준 함수인 sqrt를 쓰면 된다..

[LegenDUST]

대충 찾아보니까 요즘은 그냥 하드웨어에서 지원을 하네

[득템만세]

왠만한 수식은 이미 라이브러리화 되긴 했지
이 수식들로 뭔가를 할때 리소스 덜 먹도록 알고리즘을 짜는게 요즘식 최적화고

[숲속마을1번지🌸]

3줄 요약좀

[¡i!|!i¡]

퀘이크 3에서
개쩌는 코드가 있음
삼줄

[루에이-91123]

유명한 빠르게 제곱근 구하는 알고리즘이야..
퀘이크3 소스에 들어있어..

[도나도나도나도나]

졸트라크

[세디엘레]

아주 쉽게 설명하면..
컴퓨터 프로그램이 졸라 짱짱맨인 것 같아도...
의외로 수학적인 계산할 때 비교적 리소스를 많이 먹는데...(특히 소수점있는)
졸라 빡센 계산해야 나오는 값을..
아주 쉽게 비트단위 이동으로 대신하는 개간결한 코드를 만들었다는거임.
아주 쉬운 예를 들면 2진법에서.. 1이 한칸씩 올라가면(1을 옆으로 밀면)
00000001 -> 00000010 -> 00000100
이렇게 한칸씩 밀면 2를 곱하는 것과 같은 결과인데.. A x 2를 연산하는것보다..
비트를 한칸씩 옮기는 작업이 굳이 둘을 비교했을 때 속도면에서 엄청 빠르다는거임.

[전대미문의똥]

변수형 자료가 2개 나온다는 것 말고 아무것도 모르겠어요

[Rituals]

리커시브 함수로 되어있는걸 인라인 어셈블리로 쉬프트 연산을 조합해서 계산을 빠르게 바꾼적이 있었는데. 이것만 해줘도 워크스테이션 계산속도가 배는 빨라졌더라

[응답없음]

자료형식을 바꾸고 곱셈 뺄셈 좀 하는걸로 1/sqrt 값을 구해내는게 정상이냐아아아아아아악

[나15]

그, 그렇군!

[앙베인띠]

그러니까 수학자가 왔다 갔다는거지? 대충 이해했어.

[TLGD]

꼼수끝판왕인 건가??

[보리음료]

[직구지온잔당군]

롤코타는 어셈블리어로 만들어서 리버스 엔지니어링이 개어려웠다던데 ㅋㅋㅋ

[플마윙]

고대는 이런 일까지도 했구나

[닉에게물어보는닉네임]

전에 이거 올라오니까
이미 아트오브알고리즘 따위는 이해할 연구원급들이 만든걸
자기는 프러그래머가 이래야 한다며 어쩌구 저쩌구
하면서 반복문이 어쩌구 저쩌구 하는애봤는뎈ㅋㅌㅋㅋ

[루리웹-0179551758]

저짝 논문 나온거는 볼 때마다 살벌해.
1퍼 줄일려고 사람 갈아넣고
그게 쌓이니까 두배가 깎임

[득템만세]

이래서 프로그래머는 수학 잘해야 한다니까...
수식이 죄다 십진법 실수 기반이라, 이게 이진법에서 찐빠 안나도록 정확히 변환해야 하고
그걸 수행할 알고리즘도 부하 덜걸리고 빠르게 수행하는 방법을 연구해야 하고...

[청밥없찐]

제약속에서 빛나던 이들이
어느샌가부터 느그컴업글하면되잖?
하던 애들만 남았어ᆢ

코딩깎던 노인이 그립다

[닉에게물어보는닉네임]

엔진만드는 급이면 그거 계속할수 있음
뭐 되도않는 루프 줄이기 이런거 말고
요즘은 컴파일러가 알아서 최적화도 잘함

[득템만세]

옛날은 사람 몸값보다 하드웨어가 비싸서 사람 갈아 최적화하는게 비용절감에 도움이 되던 시대였는데
요즘은 사람 몸값이 하드웨어보다 비싼 시대가 되버려서, 최적화보다 일정 줄이는게 전체 비용절감에 더 도움이 되는 시대가 되버림...

[생쥐 백대리]

알고리즘 만드는 데에는 순수 개발자보다 타 전공자가 더 잘하지

[루리웹-4543393209]

지금의 조무사가 아닌 진짜 프로그래머들이 01로 생각하던시절 ㅋㅋㅋㅋ

[푸레양]

조무사가 왜 ㅜㅜ

[나익한]

조무사드립 쓰지 말자..

[spike _shupigel]

와 무슨소린지 전혀 모르겠어...

[GLaDOS+]

수학과 뇨속들이 전직하면 코드를 저렇게 짬
함수에 무언가 마법을 부리는데 효과가 뛰어남

[루루밍]

[Lennath_V]

수상한 애니프사 중국인 ㅋㅋㅋㅋ

[幻日のヨシコ]

근데 진짜 깃에 애니프사인데 핵고수들 있음 ㅋㅋ

[Dr.Kondraki]

몇 번을 봐도 저 발상을 어케떠올린건지 짐작조차 안 가는

[대천사 치탄다엘]

프로그래머들 특히 2000년 즈음엔 프로그래머중 진짜 천재적으로 수학을 다루는 사람이 꽤 많았지

[루리웹-3645316075]

애초에 IEEE에서 부동 실수형을 설계할 때부터 저렇게 수학적으로 작동하기 쉽게 해 준 덕분이지!

[대천사 치탄다엘]

고전게임들 소스파보면 진짜 이걸 이렇게 한다고? 미쳤네... 싶은것들 꽤있지... 요즘은 최적화를 이따구로 한다고? 미쳤네... 싶은것들이 많지만...

[도토도코]

진짜 저시대때 레인보우식스도 걸어다니고 느릿느릿했을땐데 퀘이크3는 혼자 로켓쏘고 점프대로 날라다니는데 그래픽도 좋았지..

[포근한섬유탈취제]

정확한 값을 구하는 빠른 계산법인거임? 아니면 근사값을 구해내는거임?

[루리웹-3645316075]

근사값임. 애초에 엄청나게 정확할 필요도 없음

[허접♡유게이]

근사값 구하는 거래
지금은 하드웨어 수준에서 더 정확한 걸 기본 탑재하고 있다는 듯

[루리웹-3645316075]

저 맨 아래줄 반복을 여러번 하면 정확한 값에 수렴하긴 함

[블루브루]

빠르게 근사값을 구하는거.
컴퓨터는 이진법이라 어차피 정확한 값을 요구하진 않으니 그걸 이용해서, 사용자한테 빠르게 계산결과값을 제공하기 위한 피나는 노력.

[Elina El Elisia]

이거 맨날 올려치기용으로 올라오던데
저 상수 제네가 찾은거 아닙니다 제넨 그냥 사용한거임
이거 전에 영국의 건축설계 프로그램에서도 빛과 그림자 예측용으로 사용된적이 있고
개념세우고 값 찾은건 프로그래머가 아니라 대학교수라고 알려짐

[Nuka-cola퀀텀]

아하 코드복붙이구나!

[블루브루]

와.. 이건 개발자 영역이 아니라 수학자의 영역같은데 ㄷㄷ..

[7764433482]

개멋있어