Coding/CPP 삽질기2023. 2. 26. 20:08

요즘 핫 한 ChatGPT를 유료 결제 하고, 이것 저것 질문을 해보았습니다.

Q) please explain about the John Carmack's q_sqrt function as Korean

A) 존 카맥의 q_sqrt 함수는 양의 부동 소수점 수에 대한 빠른 제곱근 근사치 함수입니다. 이 함수는 제한된 범위의 입력에 대해 빠르고 정확하게 작동하도록 설계되었습니다.

다음은 q_sqrt 함수의 C 코드입니다:

float q_sqrt(float x) {
    int i = *(int *)&x;
    i = 0x1fbd1df5 + (i >> 1);
    return *(float *)&i;
}

q_sqrt 함수는 x라는 하나의 인자를 취합니다. 이 인자는 우리가 제곱근을 계산하려는 양의 부동 소수점 수입니다. 함수는 x의 근삿값인 제곱근을 반환합니다.

함수는 먼저 포인터 캐스트를 사용하여 float 인자를 int로 변환합니다. 그런 다음 부동 소수점 수의 정수 표현은 하나의 비트만큼 오른쪽으로 시프트됩니다.

그 다음 0x1fbd1df5라는 정수 값이 오른쪽으로 시프트된 정수 값에 더해집니다. 이 값은 제곱근 함수의 근사치를 제한된 범위의 입력에 대해 얻기 위해 선택된 매직 상수입니다. 덧셈의 결과는 포인터 캐스트를 사용하여 다시 float로 변환되고 반환됩니다.

q_sqrt 함수는 [0, 2^30] 범위의 입력에 대해 빠르고 정확합니다. 그러나 입력이 커질수록 정확도가 낮아집니다. 이 함수는 표준 라이브러리의 sqrt 함수보다 정확도가 떨어지지만 더 빠르며 근사 오차는 여전히 많은 응용 프로그램에 충분히 작습니다.


  ChatGPT 가 알려준 코드는 매우 잘 돌아가는데, 코드가 이해가 가지 않아서, 이리 저리 구글링을 해보았다.

 먼저 그 유명한, 존 카맥의 고속 역 제곱근을 코드를 보고,  

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

 

고속 역 제곱근 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 고속 역 제곱근(高速逆-根, fast inverse square root)은 때때로 Fast InvSqrt()나 16진수 0x5f3759df라고도 하는, IEEE 754 부동소수점 체계의 32비트 실수에 대한 제곱근의 역

ko.wikipedia.org

아래와 같은 방식으로  sqrt(x)를 구할 수 있다는 것을 알 수 있다.

그래서 아래와 같은 코드가 나오게 됩니다.

 i = 0x1fbd1df5 + (i >> 1);

그럼 이 코드를 실행 보면,

#include <iostream>

float q_sqrt(float x) {
    int i = *(int *)&x;
    i = 0x1fbd1df5 + (i >> 1);
    return *(float *)&i;
}

float q_sqrt_new_magic_number(float x) {
    int i = *(int *)&x;
    i = 0x1fbd3ee7 + (i >> 1);
    return *(float *)&i;
}


int main(int argc, char **argv) {
    std::cout << q_sqrt(9) << std::endl;
    std::cout << q_sqrt_new_magic_number(9) << std::endl;
    return 0;
}

존 카맥 형님의 매직 넘버를 사용한게 오차률이 낮습니다. ㅠㅜ

결론:   ChatGPT가 똑똑 합니다.


 

 

'Coding > CPP 삽질기' 카테고리의 다른 글

프로그래머스 사이트 기초 문제 풀기  (0) 2023.06.07
별 그리기  (0) 2021.06.08
Stack과 Heap  (0) 2021.02.25
Posted by chobocho
Coding/CPP 삽질기2016. 4. 13. 18:00

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )


/*
From :
http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem
*/

int findMaxRect (int rect[XSIZE][YSIZE]) {
	int ret = 0;
	unsigned int x = 0, y = 0, k = 0;
	int sum[YSIZE+1] = { 0, };
	int stack[YSIZE][2] = { 0, };
	int stIdx = -1;
	int width = 0;
	int y0 = 0, w0 = 0, tempArea = 0;
	
	for ( x = 0; x < XSIZE; ++x ) { 
		for ( y = 0; y <= YSIZE; ++y ) {
			sum[y] = rect[y][x] ? ++sum[y] : 0;
		}
		sum[YSIZE] = 0;
		width = 0;
		stIdx = -1;
		for ( y = 0; y <= YSIZE; ++y) {
			if ( sum[y] > width ) {
				stack[++stIdx][0] = y;
				stack[  stIdx][1] = width;
				width = sum[y];				
			} 
			else if ( sum[y] < width ) {

				while(1) {
					y0 = stack[stIdx  ][0];
					w0 = stack[stIdx--][1];
					tempArea =  width * (y - y0);
				  
					ret = tempArea > ret ? tempArea : ret;

					width = w0;
					if( sum[y] >= width) break;
				} 
				width = sum[y];
				if ( width != 0 ) {
					stack[++stIdx][0] = y0;
					stack[  stIdx][1] = w0;	
				}
			}
		}
	}	
	
	return ret;
}


'Coding > CPP 삽질기' 카테고리의 다른 글

Bit 연산 정리  (0) 2016.08.20
printf로 디버깅 하기  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Posted by chobocho
Coding/CPP 삽질기2016. 4. 13. 17:25

#define DEBUG


#ifdef DEBUG

    #define cprintf(...) printf(__VA_ARGS__)

#else

    #define cprintf(...) 

#endif



'Coding > CPP 삽질기' 카테고리의 다른 글

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Lambda function  (1) 2016.03.17
Posted by chobocho
Coding/CPP 삽질기2016. 3. 30. 00:09

무료 C++ 컴파일러



1. 구름 IDE ( https://ide.goorm.io/ )

웹기반 IDE 이며, 기본 사용은 무료 이다.

웹 브라우져만 있으면 손쉽게 다양한 언어로 개발이 가능 하다.




2. C++ shell ( http://cpp.sh )

무료이며, 웹브라우져만 띄우면 짧은 코드를 쉽게 실행 할 수 있다.



3. Cygwin ( http://cygwin.com/install.html )

자세한 설명은 Cygwin 홈페이지를 참고하시면 됩니다.



4. Visual studio Express ( https://www.visualstudio.com/ko-kr/products/visual-studio-community-vs.aspx )

너무 유명하므로 설명은 생략 합니다.


'Coding > CPP 삽질기' 카테고리의 다른 글

printf로 디버깅 하기  (0) 2016.04.13
Lambda function  (1) 2016.03.17
Lambda function  (0) 2016.03.16
Posted by chobocho
Coding/CPP 삽질기2016. 3. 17. 00:56

[ C++ Lambda 함수 설명 ]

https://msdn.microsoft.com/ko-kr/library/dd293608.aspx

https://msdn.microsoft.com/ko-kr/library/dd293599.aspx

http://en.cppreference.com/w/cpp/language/lambda


'Coding > CPP 삽질기' 카테고리의 다른 글

C++ 컴파일러  (0) 2016.03.30
Lambda function  (0) 2016.03.16
짝수만 출력하기  (0) 2016.03.03
Posted by chobocho
Coding/CPP 삽질기2016. 3. 16. 01:02

#include <iostream>

using namespace std;


int main()

{

   int num = 2;

  

   auto sum = [](int n) -> int{ return n*n; }(num);

   

   cout << num << " " << sum << endl;

   

   return 0;

}



2 4


'Coding > CPP 삽질기' 카테고리의 다른 글

Lambda function  (1) 2016.03.17
짝수만 출력하기  (0) 2016.03.03
Couple  (0) 2015.12.23
Posted by chobocho
Coding/CPP 삽질기2016. 3. 3. 00:04

#include <iostream>

using namespace std;


int main()

{

    for (int i = 0; i < 100; i++) {

       i % 2 ||  cout << i << endl;   

    }

    return 0;

}




'Coding > CPP 삽질기' 카테고리의 다른 글

Lambda function  (0) 2016.03.16
Couple  (0) 2015.12.23
사각형 개수 구하기  (0) 2014.11.12
Posted by chobocho
Coding/CPP 삽질기2015. 12. 23. 00:42

#include <stdio.h>

#include <stdlib.h>


#define FALSE 0

#define TRUE  1



int IsSheBeautiful() { return (rand() % 101 > 99); }

int IsSheLikeMe()    { return (rand() % 51  > 49); }


int MeetGirl(int count) {

    int amIcouple = FALSE;

    

    // printf ("%d : I meet a girl!\n", count);

    

    if ( IsSheBeautiful() && IsSheLikeMe() ) {

        amIcouple = TRUE;

    }

    

    return amIcouple;

}


int Process() {

    int amIcouple = FALSE;

    int count = 0;

    

    while ( amIcouple == FALSE ) {

        amIcouple = MeetGirl(++count);      

    }

    printf ("I met %d girls\n", count);

    return amIcouple; 

}


int main(int argc, char **argv) {

    printf("%s\n", Process() == TRUE ? "I am not a single!" : "I am a sigle");

    return 0;

}


'Coding > CPP 삽질기' 카테고리의 다른 글

짝수만 출력하기  (0) 2016.03.03
사각형 개수 구하기  (0) 2014.11.12
Mirror  (0) 2014.10.27
Posted by chobocho
Coding/CPP 삽질기2007. 4. 24. 00:49

#include <stdio.h>


void process(void);

void showBit(int n);



int main (int argc, char **argv) {

    process();

    return 0;

}


void process(void) {

    int          nSignNumber   = 0xFFFFFFFF;

    unsigned int nUnSignNumber = 0xFFFFFFFF;

    

    printf ("Original :\n%d %u\n", nSignNumber, nUnSignNumber);

    showBit(nSignNumber);

    showBit(nUnSignNumber);

    

    nSignNumber   <<= 1;

    nUnSignNumber <<= 1;

   

    printf ("<< 1 :\n%d %u\n", nSignNumber, nUnSignNumber); 

    printf ("%d %u\n", nSignNumber, nUnSignNumber);

    showBit(nSignNumber);

    showBit(nUnSignNumber);


    nSignNumber   >>= 1;

    nUnSignNumber >>= 1;

    

    printf (">> 1 :\n%d %u\n", nSignNumber, nUnSignNumber); 

    printf ("%d %u\n", nSignNumber, nUnSignNumber);

    showBit(nSignNumber);

    showBit(nUnSignNumber);    

}


void showBit(int n) {

    for (int i = 31; i >= 0; i--) {

        printf ("%d%s", ((n & 1<<i)?1:0), ((i % 4 == 0)?" ":""));

    } 

    printf ("\n");

}



int에 >> 연산자를 적용할 경우, 제일 왼쪽 비트가 그대로 복사 됨

unsigned int인 경우 0으로 채워짐 



Hi-iMac:CPP chobocho$ ./a.out

Original :

-1 4294967295

1111 1111 1111 1111 1111 1111 1111 1111

1111 1111 1111 1111 1111 1111 1111 1111

<< 1 :

-2 4294967294

-2 4294967294

1111 1111 1111 1111 1111 1111 1111 1110

1111 1111 1111 1111 1111 1111 1111 1110

>> 1 :

-1 2147483647

-1 2147483647

1111 1111 1111 1111 1111 1111 1111 1111

0111 1111 1111 1111 1111 1111 1111 1111


'Coding > CPP 삽질기' 카테고리의 다른 글

심심풀이 프로그래밍...2  (0) 2007.09.17
별 그려주는 코드  (0) 2006.08.22
입력 버퍼비우기  (0) 2006.02.23
Posted by chobocho