퀘이크의 빠른 역 제곱근 이해

기사와 연구 논문은 게임 퀘이크에서 사용되는 역 제곱근($1/\제곱근$)을 계산하는 빠르고 마법처럼 보이는 방법을 설명합니다.

나는 그래픽 전문가가 아니지만 제곱근이 유용한 이유를 고맙게 생각합니다. 피타고라스의 정리는 점 사이의 거리를 계산하고 거리로 나누면 벡터를 정규화하는 데 도움이됩니다. (정규화는 종종 분할에 대한 멋진 용어 일뿐입니다.)

지진과 같은 3 차원 게임은 매초마다 거리 엄청나게(예 엄청나게)로 나누므로”사소한”성능 향상이 대단히 도움이됩니다. 우리는 제곱근을 가지고 정규적인 방법으로 나누기를 원하지 않습니다:지수와 나눗셈은

내 이해:이 놀라운 해킹은 뉴턴의 근사 방법을 사용하여 역 루트를 추정하고 훌륭한 초기 추측으로 시작합니다.

추측을 만들기 위해,그것은 과학적인 표기법에 부동 소수점 숫자를 취하고,&반 지수를 부정하는 것은 뭔가 역 제곱근 가까이 얻을 수 있습니다. 그런 다음 뉴턴의 근사 방법의 라운드를 실행 더 추정치를 구체화하고 타다,우리는 역 제곱근 근처에 뭔가를 가지고있다.

뉴턴의 근사 방법

뉴턴의 방법은 모든 함수의 근사 뿌리를 찾는 데 사용할 수 있습니다. 이 방법을 반복하여 루트에 점점 더 가까이 다가 갈 수 있지만이 기능은 1 단계 만 사용합니다! 여기에 뉴턴의 방법에 대한 충돌 코스가 있습니다(그것은 나에게 새로운 것이 었습니다):

당신은(공식에 새로운 추측에 연결)이 과정을 반복 유지하고 루트에 대한 가까운 근사치를 얻을 수 있습니다. 결국 당신은 에프(새로운 추측)를 정말로,정말로 0 에 가깝게 만드는”새로운 추측”을 갖게됩니다. (또는 그들이 말하는 것처럼 정부 업무에 충분히 가깝습니다).

분명히,우리는 우리의 오류를 가능한 한 작게 만들고 싶습니다. 즉,오류를 만드는”엑스”를 찾는 것을 의미합니다(엑스)=0,이는 오류 방정식의 루트를 찾는 것과 같습니다. 우리가 오류를 연결하면(엑스)뉴턴의 근사 공식에:

그리고 적절한 파생 상품을 가져 가라.:

우리는 더 나은 추측을 위해 공식을 얻기 위해 그들을 연결할 수 있습니다:

위의 코드에서 볼 수있는 방정식은 정확히 다음과 같습니다.엑스 우리의 새로운 추측(지)과”엑스 하프”는 원래 값의 절반입니다($0.5 나는$):

x = x*(1.5f - xhalf*x*x);

이 공식을 사용하면 추측”지”로 시작하고 공식을 반복하여 더 나은 추측을 얻을 수 있습니다. 역 제곱을 찾기 위해 여러 반복을 사용하는이 데모를 사용해보십시오:

그래서 내 친구,질문이된다:”우리는 어떻게 좋은 초기 추측을 할 수 있습니까?”

좋은 추측 만들기

역 제곱근에 대한 좋은 추측은 무엇입니까? 그것은 약간의 트릭 질문입니다-역 제곱근에 대한 최선의 추측은 역 제곱근 그 자체입니다![2983][3253][3253][3253][3253][3253][3253][3253][3253][3253][3253][3253]

이 곳에서 마법이 시작됩니다. 지수 형식이나 과학적 표기법에 숫자가 있다고 가정해 봅시다:

이제 정규 제곱근을 찾으려면 지수를 2:

그리고 역제곱근을 원하면 지수를-2 로 나누어 부호를 뒤집습니다:

그래서,우리는 어떻게 다른 값 비싼 연산 없이 숫자의 지수를 얻을 수 있습니까?

수레는 가수 지수 형식

에 저장됩니다. 부동 소수점 숫자는 가수 지수 형태로 컴퓨터에 의해 저장됩니다,그래서 지수를 추출하고 분할 할 수 있습니다!

그러나 명시 적으로 나누기를 수행하는 대신(중앙 처리 장치에 비용이 많이 든다)코드는 또 다른 영리한 해킹을 사용합니다. 한 위치에 의한 오른쪽 이동은 2 로 나누는 것과 같습니다(2 의 제곱에 대해 이것을 시도 할 수 있지만 나머지는 잘립니다). 그리고 음수를 얻고 싶다면-1 을 곱하는 대신(곱셈은 비쌉니다)”0″에서 숫자를 빼십시오(빼기는 저렴합니다).

따라서 코드는 부동 소수점 숫자를 정수로 변환합니다. 그런 다음 비트를 1 씩 이동시킵니다.이 비트는 지수 비트를 2 로 나눈 값입니다(결국 비트를 다시 플로트로 바꿀 때). 그리고 마지막으로 지수를 부정하기 위해 매직 넘버에서 뺍니다. 이것은 몇 가지 작업을 수행합니다:가수(비 지수 부분,일명 5:$5\10^6$)를 보존하고,홀수-짝수 지수를 처리하고,지수에서 가수로 비트를 이동하고,모든 종류의 펑키 한 물건. 신문은 자세한 내용과 설명을 가지고,나는 주위에 처음으로 그것을 모두 잡을하지 않았다. 언제나처럼,당신은 무슨 일이 일어나고 있는지에 대한 더 나은 설명이있는 경우 의견을 주시기 바랍니다.

결과는 우리가 진짜 역 제곱근에 정말 가까운 초기 추측을 얻을 수 있다는 것입니다! 그런 다음 우리는 추측을 구체화하기 위해 뉴턴의 방법을 한 번 할 수 있습니다. 추가 계산 비용으로 더 많은 라운드가 가능하지만 한 라운드는 필요한 정밀도를 위해 필요한 모든 것입니다.

그럼,왜 매직 넘버?

위대한 해킹은 정수와 부동 소수점 숫자가 저장되는 방법입니다. $5 와 같은 부동 소수점 숫자.지수를”5.4″보다 별도의 비트 범위에 저장하십시오. 전체 숫자를 이동할 때 지수를 2 로 나누고 숫자(5.4)를 2 로 나눕니다. 이것은 매직 넘버가 들어오는 곳입니다.이 나눗셈에 대한 몇 가지 멋진 수정 작업을 수행합니다. 그러나 사용할 수있는 몇 가지 매직 넘버가 있습니다.이 숫자는 가수의 오류를 최소화하는 데 발생합니다.

매직 넘버는 짝수/홀수 지수에 대한 수정;신문은 또한 사용하는 다른 매직 넘버를 찾을 수 있습니다 언급하고있다.이 웹 사이트는 웹 사이트를 탐색하는 데 도움이 될뿐만 아니라 웹 사이트를 탐색하는 데 도움이 될 수 있습니다.:

• http://games.slashdot.org/article.pl?sid=06/12/01/184205 그리고 내 의견

이 시리즈의 다른 게시물

1. 숫자 시스템 및 기지
2. 가이드에 대한 퀵 가이드
3. 지진의 빠른 역 제곱근 이해
4. 컴퓨터 네트워킹에 대한 간단한 소개
5. 엔디안 바이트 순서
6. 유니 코드와
7. 이진 파일 형식에 대한 약간의 디디
8. 정렬 알고리즘