John Carmark 비밀번호 기반 상세 설명
2746 단어 JohnCarmark 비밀번호
/*================SquareRootFloat================*/
float SquareRootFloat(float number) { long i; float x, y; const float f = 1.5F; x = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); //이 줄 조심 하 세 요. y = * ( float * ) &i; y = y * ( f - ( x * y * y ) ); y = y * ( f - ( x * y * y ) ); return number * y;}
x5f3759df？ 이것 은 무엇 입 니까?수치 분석 을 배 워 보면 알 수 있 듯 이 알고리즘 에서 제곱 근 을 구 하 는 것 은 보통 무한 접근 방법 을 사용 하 는 것 이다.예 를 들 어 뉴턴 교체 법 은 그 당시 에 제 수치 분석 을 너무 못 해서 잘 말 하지 못 했 습 니 다.쉽게 말 하면 5 의 제곱 근 을 구하 고 추측 치 를 선택 하 는 것 이다.예 를 들 어 2 를 선택 하면 우 리 는 이렇게 계산 할 수 있다.
/2 = 2.5; 2.5+2/2 = 2.25; 5/2.25 = xxx; 2.25+xxx/2=xxxx...이렇게 반복 해서 교체 하면 결 과 는 반드시 sqrt(5)에 수렴 됩 니 다.맞습니다.일반적인 제곱 근 을 구 하 는 것 은 모두 이렇게 계산 합 니 다.한편,카 마크 의 차이 점 은 그 가 신비 한 추측 치 인 0x5f3759df 를 시작 으로 전체 접근 과정의 수렴 속 도 를 폭등 시 켰 다 는 점 이다.Quake III 가 요구 하 는 정밀도 10 의 마이너스 3 차원 에 대해 한 번 의 교체 만으로 결 과 를 얻 을 수 있다.
좋아,이것 도 소 b 가 아니라면 이어서 보 자.
퍼 듀 대학의 수학자 크 리 스 로 몬 트 는 이 를 보고 재 미 있 었 다.카 마크 가 내 놓 은 이 추측 치가 어떤 비밀 이 있 는 지 연구 하기 로 했다.Lomont 도 소인 이다.정성 을 들 여 연구 한 후에 이론 적 으로 도 가장 좋 은 추측 치 를 도 출 해 냈 고 카 마크 의 숫자 와 매우 비슷 하 다.0x5f 37642 f.카 마크 는 정말 대단 합 니 다.그 는 외계인 입 니까?
전설 은 여기 서 끝나 지 않 았 다.로 몬 트 는 결 과 를 계산 한 후에 매우 만 족 스 러 웠 다.그래서 자신 이 계산 한 시작 값 과 카 마크 의 신비 한 숫자 를 가지 고 경 기 를 해서 누구의 숫자 가 더 빠 르 고 정확하게 제곱 근 을 구 할 수 있 는 지 보 았 다.결국 카 마크 가 이 겼 다.카 마크 가 어떻게 이 숫자 를 찾 았 는 지 아무 도 모른다.
마지막 으로 로 몬 트 는 화가 나 서 폭력 적 인 방법 으로 숫자 하나,숫자 하 나 를 시험 해 보 았 다.마침내 카 마크 숫자 보다 조금 더 좋 은 숫자 를 찾 았 다.비록 실제로 이 두 숫자 가 발생 한 결 과 는 매우 비슷 하지만 이 폭력 으로 얻 은 숫자 는 0x5f375a 86 이다.
로 몬 트 는 이 를 위해"패스 트 인 버스 스 퀘 어 루트"라 는 다음 논문 을 썼 다.
나 는 이 함 수 를 C\#로 쓰 면 된다. 32,33 줄 은 두 번 의 뉴턴 교체 법 을 사용 하여 일정한 정밀도 에 이 르 렀 다.물론 너 도 스스로 정 도 를 제어 할 수 있 고 Y 의 제곱 근 의 역 수 를 구 했 기 때문에 마지막 에 number*y 로 되 돌아 갔다.
SquareRootFloat 함수 의 가장 관건 적 인 한 마디 는 i=0x5f3759df-(i>>1)이다.다음은 그 부분 에 대한 설명 이다.
뉴턴 교체 법의 가장 관건 적 인 부분 은 첫 번 째 근사 근 을 추정 하 는 데 있다.이 근사치 근 이 진 근 과 충분히 가깝다 면 몇 번 의 교체 만 있 으 면 만 족 스 러 운 해 를 얻 을 수 있다.
이어서 우 리 는 첫 번 째 근사 근 을 예측 할 방법 을 강구 해 야 한다.이것 도 위의 함수 가 가장 신기 한 곳 이다.그것 은 어떤 방법 을 통 해 진 근 과 매우 가 까 운 유사 근 을 계산 해 냈 기 때문에 교체 과정 을 한 번 만 사용 하면 비교적 만 족 스 러 운 해 를 얻 을 수 있다.얘 는 어떻게 했 지?모든 오묘 함 은 이 줄 에 있다.
i = 0x5f3759df - (i >> 1); // 계산 첫 번 째 근사 근
아주 이상 한 문구 아 닙 니까?하지만 곰 곰 이 생각해 보면 이해 할 수 있 습 니 다.float 형식의 데 이 터 는 32 비트 시스템 에서 이렇게 표 시 됩 니 다.
bits:31 30...031:기호 위치 30-23:총 8 비트,보존 지수(E)22-0:총 23 비트,보존 끝자리(M)
그래서 32 비트 의 부동 소수점 은 10 진법 실수 로 M*2^E 라 고 표시 합 니 다.뿌리 를 내리 고 꼴찌 는 M^(-1/2)*2^(-E/2)입 니 다.지금 은 분명 해.구문 i>>1 그 작업 은 지 수 를 2 로 나 누 어 2^(E/2)를 실현 하 는 부분 이다.앞에서 상수 로 그것 을 빼 면 M^(1/2)를 얻 고 모든 지수의 기 호 를 반전 시 키 는 것 이 목적 이다.
좋은 웹페이지 즐겨찾기
