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

[테헤란]

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

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

수정1: 오타랑 수식 잘못 집어넣은 부분 정정

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

[Bolic]

ㅁㅊ 이게됨?

[야황 육손]

완벽하게 이해했어

[야황 육손]

그러니까 저거 복사해서 쓰면되는거지?

[CTI92]

ㅔ

[Mystica]

저래서 수학 고인물이 필요하댔나

[CTI92]

하 이게 프로그래밍이지 ㅋㅋㅋ

최적화하려면 저 정도 수준까지 알아야하는구나

[간사합니다]

what the f■ck?

[아이리오 아키]

맞음. Q3 코드도 카멕형이함

[아이리오 아키]

참고로 저거 99년 게임이고 C로 짜진 엔진이다.

[cherryade]

역시 과메기형

[옥땅이]

ㄷㄷ 역시 128류 개발자

[식신시츄]

개발은 혼자 다 하면 되니 사람 숫자 늘려서 의사소통에 시간 낭비하면 안된다고 하던 양반이니 직접 다 했겠지

[아이리오 아키]

그래서 주석에 시X 저기 머꼬? 라는게 적혀있잖음ㅋㅋㅋㅋㅋ

[식신시츄]

주석 단 사람 심정 ㅋㅋㅋㅋ

[아이리오 아키]

ㅋㅋㅋㅋㅋㅋ

[부랄번호-7376676754]

존 카멕이 둠 3에 들어간 광원효과도 직접 다 코딩했음

[여포신봉선]

암튼 게임 만드는데 수학자가 필요하다는거지?

[페르메르]

수학자보다는 개발자가 수학적 사고와 친숙하고 컴퓨터의 구조를 잘알아야 한다는 거에 가까움

[네크로노미콘속독대회]

허용범위 내의 오차가 있지만 그대신 무지막지하게 연산이 줄어드는 기법들 보다보면

전 그냥 ㅂㅅ이구나 라는것만 느끼게 됬죠. 대학 과목중에 이게 있어서 3개월은 ㅂㅅ된 기분이었는데

[청새리상어]

와씨 와드

[아이리오 아키]

Q3 개발진이라고 뭉뜽그리기보다 카멕형이 만든거라고 봐야할거같다ㅋㅋ

[식신시츄]

이드 개발진 = 존카멕 공식은 레이지때까지 거의 유효했음.. 개발은 나 혼자 다 하면 된다던 사람이라..

[아이리오 아키]

그럿타.

둠3 엔진 만들때 C++로 처음 넘어간 양반일 정도로 효율을 되게 따진모양

[AbsoluteOne]

이해했음
저 코드를 복사하면 된다는거지?

[키사라기_치하야]

사실 API 이용하는 수준에서는 저런 수학 쓸 일도 적겠지만

저런 API를 만드는 입장에서는 대학원 석박사들이 모여서 저런 수학 이야기만 하겠지 무섭다

[Magincia]

그럼 지금 기술은 저거보다 더한 게 많단 말이겠네..
와..

[V_solves_everything]

요즘게임은 저걸 어떻게 극복했을까

[간사합니다]

압도적인 성능을 기반으로 처리능력이 딸리면 구린 컴퓨터 쓰는 유저탓을 함

[감정지배자]

요즘은 하드웨어가 좋아서 대부분 최적화 필요없음

[루리웹-7096737729]

요샌 그냥 컴파일러가 알아서 저런 코드로 바꿔줌. 저런 거 하느라 생산성 낭비하느니 그냥 다른 코드 한줄을 추상적으로 더 짜고 최적화는 대부분 컴파일러한테 떠넘기면 됨. 오히려 어줍잖게 최적화한다고 깝치면 컴파일러 최적화가 제대로 안 돌아서 더 느릴수도 있음

[루리웹-8811529276]

이게 맞말이지 이젠 그냥 루트쓰면됨
퀘이크3는 1999년대 게임이니까 그런거지

[혼노모]

지금은 극한환경에서 동작할 임베디드 머신 만들게 아니라면 저런 방법을 쓸 이유가 없어졌어

[감정지배자]

게임 개발 안할거면 수학 필요없는게 맞음

[건담잘그리고싶다]

???

[Cadillac Touring]

아주 틀린 말은 아니지

[루리웹-8811529276]

이제 하드웨어 좋아져서 게임이나 임베디드 아니면 굳이 수학잘할 필요없는게 맞긴함

[foo@bar]

다른 프로그래밍은 수학 안쓸것 같지? 요새 유행하는 인공 지능만 해도 수식 덩어리이고, DB도 수학 기반이고.. 하나못해 반복문 돌리는것도 기초적인 산수 필요함

[zegox2]

생각보다 게임 말고도 수학이 많이 들어가는 분야는 많아요.

[morecomplex]

게임 개발을 안 할 거면 수학이 필요없다라기보단,
게임 개발이 그만큼 프로그래밍 중에서도 가장 어려운 축에 속한다고 보면 정확함.
'나도 게임 만들어보고 싶어' 라는 건 '나도 초정밀 뇌수술 한 번 해 보고 싶어' 같은 말과 비슷하다고 보면 될 듯?

[힙합거러지]

나도 개발로 밥벌어 먹고 산지 10년정도 됐는데 수학쪽이 약해서 어디가서 개발자라고 얘기 안함.
그냥 개잡부 입니다. 이렇게 얘기하지

[ズドン巫女]

프로그래밍은 그런이야기 잘 안나오지. 처음 발 담글때부터 닥치고 수학이라
것보다 기획에서 많이나옴. 그림못그리고 프로그래밍 못하는데 게임개발 하고싶은애들이 많다

[루리웹-9308200273]

1/sqrt 가 저렇게까지 해야하는거였나...

[Πλωτῖνος]

수학과가 괜히 컴공으로 발돌린다는게 아니긴 하지

[⎝⎝⎛° ͜ʖ°⎞⎠⎠]

뭔소리지

[렌탈안구]

좋아 이해해써

[길티네]

뇌가 이진법으로 되어있으신가ㄷㄷ 미쳤다;;

[건담잘그리고싶다]

진짜 존카멕은 전설이다

[GRIS]

무슨소리야 시팔

[Lucir]

수학자가 괜히 알고리즘 개발하는게 아니지

[루리웹-0890957404]

광원효과 코드 와드

[놀라운닉이떠올랐지만여백이모자라]

이런거보면 내가 월급받고 개발하고있는게 너무 죄송스러워진다
흑흑

[바스커빌]

나도 왓더퍽 이라고 주석 달았겠다. 뭐야 왜되는데? 하면서 수학자 입장에서는 쉽게 이해?할것 같다만 프로그래머 입장에서 느낌이 방정식 쉽게 계산하는거 찾다가 혹은 우연히 코드 찾아서 넣었더니 너무 잘작동되서 기분은 좋은데 정확하게 이해못해서 말한기분 ㅋㅋㅋㅋ

[코드게이]

와 아이디어 대단하다

[샌드참샌드]

광원효과 코드 와드

[하늘서리]

왓더퍽

[코드게이]

근데 뉴턴 랩슨법이나 이런 계산 수치계산쪽도 자세히 알아야하겠네

[려니]

고등학교때로 돌아가면 수학따위 아무쓸모없다고 생각한나에게 죽빵때리고싶다

[열역학2법칙]

당연히 실생활에서는 그다지 필요 없음. 프로그래머나 공학 직업 가진 사람에게 필요하지....ㅋㅎㅎㅎ

[려니]

직업이 공학쪽이라서.....

[열역학2법칙]

ㅠㅠ 왜 공부 안했어

[캌테일]

두렵다..

[Earthy]

결국에 근사값 최대한 이용해서 식 간단화했다는 거네.
컴퓨터 성능이 이걸 그냥 시켜도 사실상 프레임에 영향이 없을 정도로 발전한 지금은 이럴 필요는 없겠지.

[PALzoa]

컴퓨터 구조에 관한 명확한 지식이 없으면 할 수 없는

[감자is뭔들]

와 비트연산 극한을 여기서 보네 이게 뭐시에요

[kbsd1234]

???:아 난 게임만들거라서 수학공부는 안해도 된다고!

[bewayt]

와드

[LVCIVS BRVTVS]

그전에 오차를 교정하는 수식도 있다는게 넘모 놀랍다

[틴캘코나이트]

자신감이 떨어졌어

[ズドン巫女]

슈팅게임에서 주인공 기체따라 날라오는 좌/우편향 총알이나 주인공 기체가 쏜 총알이 긋는 궤적같은것도 방정식이 한덩어리씩 들어가지.
난 이전기획자가 넘겨둔 문서 그대로 개발에 던졌다가 개발이랑 같이 자빠졌었다. 소수점포함 8자리 숫자 하나 구할라고 10^33까지 올라갔다가 00.000000까지 내려오는 계산식을 만들어뒀더만. 수식 바꾸느라 둘이서 한달동안 대가리터짐. 난 안그래도 수학도 잘 못하는데 씨부럴..

[잠보곰]

https://youtu.be/DEqXNfs_HhY
이런거 보면 수학하시는 분들 존경스러움

[E캔두잇]

빠른 제곱근 코드 와드

[소켓통신]

쩌네요

[Sanith]

한국인이면 한국말로 해르

[쿠로가]

정확한 계산은 수학자들 몫이지
우리 공학자들은 적당한 보정값만 구해서 최고 효율만 원한다고

[루리웹-2235448]

간단하게 6을 구하시오 하면
1+1+1+1+1+1로 더하기로 하냐
2×3하냐 해서 컴퓨터가 리소스 덜 잡고 빠르게
값을 구할때 수학이 중요하다는거

[TopSpoiler]

https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%EC%97%AD_%EC%A0%9C%EA%B3%B1%EA%B7%BC

"이 알고리즘은 1990년대 초에 실리콘 그래픽스에서 개발한 것으로 추정되며, 1999년에 퀘이크 3 아레나의 소스 코드에 쓰인 것이 가장 유명하다."

카맥이 만든게 아님.

"이 알고리즘은 뉴턴의 방법을 사용하여 비교적 정확한 결과를 만들어 내지만, 소수점의 손실 때문에 부정확하고 1999년부터 도입된 x86 SSE의 rsqrtss에 비해 훨씬 느리다."

요새는 FPU가 더 빠르고 정확해서 안 씀

[FreeHK]

카맥이 쓴건 저 왓더 뻑 이라는 주석이라는 소리
카멕도 다져다 복 붙했....

[루리웹-1055810202]

그래서 저 함수를 걍 컨트롤C 컨트롤 V 하면 된다는거지?

[이상한]

ㄴㄴ 라이브러리화 되어있으니 불러오기 하면 됨

[루리웹-1055810202]

컴파일러가 최적화 까지 다해준다니 개쩐다

[SSAMDASU]

먼말이야 슈바

[테헤란]

[카오틱블레이드]

저게 이해 안되면 이걸 생각하면 됨
1. pc에서 1부터 10000 까지 더한 결과를 내야 되는 경우가 있음.
2 단순한 프로그래머는 반복문을 이용해서 1+2+3.... 해서 10000 까지 더함. - 이러면 덧셈을 9999번 하는 거.
3. 그런데 옆에 지나가는 수학자가 (10000+1)x10000/2 라는 수식을 가르쳐줌. - 한번의 덧셈과 곱셈과 나눗셈으로 끝.

라이브러리 단계로 가면 이런게 꽤 있음

[루리웹-1055810202]

컴퓨터에게

수학을 노가다 시켜서 풀게 하냐

아니면 수식을 간단화해서 풀게 하냐의 차이같네

[byluk]

와,,, 개쩌네
본체의 연산능력을 이용해서 아예 프로그램이 해결하게 할거냐
아니면 식을 간소화 할거냐 캬 수학 좋아했었는데 역시 쩐다

[auaua]

비트연산이란 경우의 수를 생각하는 것부터 다르다.

[페니블루]

광원 와드

[내가내라꼬]

전혀 모르겠다.

//그래서 큰 업적 세우신 분들 보면 항상 수학자분들이랑 협업을 하지.. 막말로 나는 이론을 만들테니 너는 증명해라 ㅋㅋㅋㅋ

[다세포됨]

코드 읽다가 저 0x5f3759df에서 주석처럼 왓더뻑이란 생각이 듬 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
솔직히 용도는 몰라도 어떤 계산이 이루어지는구나 하는건 이해가 가는 간결한 코드임 저 32비트짜리 수 빼면 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[루리웹-1055810202]

역시 수학은 대가리를 써서 풀어야돼 노가다로 풀면안돼고

[왕사자]

어차피 곱셈 나눗셈은 코드로 접근하면 모두 가산기(+)를 통해 처리되어

비트 단위 덧셈과 비트 쉬프트, 오버로드 등으로 처리됨.

그 어셈블리 코드를 이해하면 적용 가능한 수준이긴 하지만.. 역시 WTF이군.

참고로 퀘이크의 존 카멕은 어쎔블러로 프로그램 하던 사람임.

어셈블러(기계어를 영문자로 치완한, 즉, 기계어와 1:1 메칭되는 언어)

물론 이후 세대부터는 컴파일 과정을 포함해서 1:1이라기는 좀 그렇게 되었지만, C나 basic, java처럼 보고 이해가기 쉽게 만들어진 언어는 아님.

간단한 C코드 Disassamble하면 장난아닌 길이의 코드가 나온다.(물론 컴파일러의 최적화와 관련 있긴하지만.)

[kernel panic]

math 라이브러리에 이런 류의 접근이 많음. sin cos 구할 때나 log 구할 때 미리 연산된 테이블을 참조함.

[으이히힝]

쉽게 말하면 Float의 데이타 구조가 로그형태를 띄는걸 역이용해서 적절한 상수랑 연산만으로 1/sqrt 계산이 가능하다는건가? 발상지리네 ㄷㄷㄷㄷ

[세피넬리아]

지금은 걍 공식 그대로 써도 알아서 빌드할 때 맞춰서 빌드한다.

[노말맨]

이해가 안가는데 정상이죠?

[시카요]

저런거 보면 어떻게 저런 생각를 하는지 궁금함

[에마텐]

내가 하는건 프로그래밍이 아니구나..

[세피넬리아]

저란건 api 개발 같은 로우레벨 언어 쓰는 개발자들이 신경써야 할 부분이지 일반적인 클라이언트 개발하는 하이레벨 언어 쓰는 사람이 신경 쓸 부분이 아님.

하이레벨 개발자들은 저런식으로 만들면 오히려 욕처먹음. 유지보수 거지같이 만든다고.

[세피넬리아]

무엇보다도 어줍잖게 저런거 따라해봐야 전문적으로 api 개발하는 사람들이 만들어 놓은 성능 절대 못따라감.

[우아카리]

수학적으로 다른 연산을 써서 근사값을 내는 건 자주 있는 일이라 아주 놀랍진 않은데,
거기다 변수 데이터 저장 형식을 응용해 연산과정을 줄이는 건 생각도 못했네.