[CSAPP] 부동소수점 부분 공부하다가 발견한 신기한 알고리즘 1/sqrt(x)

출처: 1/sqrt(x)를 빠르게 구하는 알고리즘 _ Fast InvSqrt() : 네이버 블로그 (naver.com)

1/sqrt(x)를 빠르게 구하는 알고리즘 _ Fast InvSqrt()

컴퓨터가 숫자를 어떻게 비트로 표현하는지 배우는 부분에서 부동소수점 부분을 배우게 되는데 IEEE754 표준을 공부하다가 왜 지수부에 bias를 더하는지 이유를 알고싶어서 검색를 하다가 컴퓨터가 수를 저장하는 원리를 사용하여 극한으로 계산을 최적화한 사례로 소개되어있길래 알게되었다.

 

바로 1/sqrt(x)를 구하는 연산인데 이게 필요한 이유는 벡터를 단위벡터로 만들 때 크기로 나눠주는 과정 이라고 한다.(대충 예상해보자면 3d게임에서 뭔가 필요하지않을까..?)

 

이 연산을 최적화 하는 핵심은 논리연산과 비트연산을 컴퓨터가 훨씬 빨리 잘 하기때문에 이를 극한으로 사용하는것인데 Newton's Method 와 같이 수학이 나오는 부분까지는 전부 이해하지는 못했지만 0x5f3759df - (i >> 1)를 구한 뒤 float로 바꿔주는 것만 하면 1/sqrt(x)를 구할수있다는 결과가 너무 신기했다.

 

컴퓨터 시스템을 low레벨까지 알면 이런 괴물같은 최적화도 가능하다는걸 느끼게 해주는 좋은 예시였던거같아서 글로 남겨보았다.