나의 큰 O는 log x야

저번에 제곱근 함수를 구현해본것에 이어서 밑을 e(2.71828..)로하는 지수함수 exp에 대해 구현해보자. exp(x)의 테일러 전개식이다. 다행이도 exp(x)의 전개식은 어떤 x에 대해서도 성립한다. 그럼 그냥 간단히 저 식을 구현하는걸로 exp구현을 끝낼수 있지만, 역시 프로그래머에게는 속도가 중요하다. 그래서 다음과 같이 식을 변형해보자. (단, )가 된다. 는 어차피 부동소수점데이터에서 지수부로 곧바로 들어갈테고 만 계산하면 된다. 그런데 ln2=0.693147.. 이므로, α는 ln2보다 작으므로, 테일러 전개에서 x의 차수가 높아질수록 항의 값은 작아질 것이다. 이제 필요한 정밀도까지 계산해 내려가면 된다. float(32비트 부동소수점형)같은 경우 정밀도가 23비트이므로 항이 보다 작아..

프로그래밍/테크닉 2008. 11. 28. 00:35

우리가 프로그래밍을 하면서 자주 사용하는 여러 수학 함수들이 있다. 할일 없는 사람들은 이 함수들이 어떻게 작동하는지 정말 궁금해할지도 모른다. (물론 나도 그런 할 일 없는사람이다.) 한 번 내가 알고 있는 것들을 글로 써보며 생각을 정리해보고자 한다. 수학함수를 구현할때 가장 중요한 점은 정밀도와 속도이다. 늘상 있는 일이지만 프로그래머는 정확성과 속도 사이를 잘 조율해야한다. 필요이상의 정밀도는 시간 낭비일뿐이다. 먼저 수학함수 중에서 가장 인기가 높은 제곱근 함수 (sqrt함수) 거리 구할때를 비롯하여 안 쓰이는 곳이 없는 인기 좋은 함수이다. 한번 float sqrt(float x)를 구현해보자. 부동소수점 데이터는 꼴로 표현된다. (음수일 경우와 0일 경우는 무시했다.) 여기서 두 가지 경우로..

프로그래밍/테크닉 2008. 11. 26. 00:45

디시인사이드 프갤의 디- 횽의 코드가 아트 코딩/변태 코딩의 시작이라고 할수 있다. int main() { int score; puts("점수를 입력하세요."); scanf("%d",&score); printf("자넨 %c일세.","FFFFFEDCBAA"[score/10]); } 위 코드는 학점을 계산해주는 코드인데, 점수는 0에서 100사이이다. 정말로 아름답지 않을수가 없는 코드이다. 코딩의 르네상스를 가져왔다고나 할까..

프로그래밍/테크닉 2008. 11. 12. 20:08

BCD는 이진화십진코드(2진수 4비트를 묶어서 10진수 한자리를 나타내는 코드)의 약자. 따라서 BCD는 십진수로 표현하기가 쉽다. 하지만 일반적인 2진수는 10진수로 나타내는게 쉽지가 않다. 그래서 사용하는 알고리즘이 시프트 더하기 3 알고리즘, (double dabble)알고리즘이다. 이 알고리즘은 간단하게 설명하면 다음과 같다. 일반 2진수 코드를 왼쪽으로 1비트씩 시프트한다. 4비트씩 묶어서 5 이상이 되는 자리에는 3을 더해준다. 모든 비트가 다 왼쪽으로 시프트 될때까지 위 과정을 반복한다. log2=약 0.3010 이므로 십진수 한자리를 표현하려면 약 3.33비트가 필요하다. 예를 들어 이진수 11001100을 BCD코드로 변환해보자. 대략 BCD코드가 3자리 필요할거다. 0000 0000 0..

프로그래밍/테크닉 2008. 7. 10. 10:29

DWORD보다 큰 정수를 더하는 코드는 전에 정리해놓았지만, DWORD보다 큰 정수를 어떻게 입력받고, 출력하지?? 방법은 단 한 가지, 문자열로 받고,문자열로 내보낸다. 그러기 위해서 double dabble이라는 알고리즘을 사용한다. 쉬프트 더하기 3 알고리즘이라고 카더라 long CreateFiString(Fi& fi,const char* number) { long Sign=0; if(*number=='-')Sign=1,number++; else if(*number=='+')number++; DWORD len=(DWORD)strlen(number); DWORD sn=(10*len+2)/3; fi.Size=(sn+31)>>5; DWORD i=(len+7)>>3; fi.pData=new DWORD[fi..

프로그래밍/테크닉 2008. 7. 9. 00:31

흔히 빅 인터거(Big Integer)라고 부르기도 하는 방법. 큰 수를 여러 작은 수로 쪼개는 것이 해결방법. inline DWORD _iladdss(DWORD* po,DWORD* pr,DWORD count) { if(count==0)return 0; DWORD carry=0; __asm{ push esi; clc; cld; mov esi,pr; mov ebx,[po]; mov ecx, count; //반복회수 count로 지정 iloop: lodsd; adc [ebx],eax; //*po값에 *pr을 더함 inc ebx; inc ebx; inc ebx; inc ebx; loop iloop; //반복실행 jnc icarry; mov carry,1; icarry: pop esi; }; return car..

프로그래밍/테크닉 2008. 7. 9. 00:05