나의 큰 O는 log x야

c++ 클래스를 이용하면 사용할 때 편리한데, 무거워지는 느낌이 있어서, 귀찮지만 c로 구현한다. 먼저 Big Integer를 위한 구조체를 다음과 같이 정의한다. typedef struct tagbigint{ u4 len; u4* dats; }bigint; len은 dats배열의 길이를 나타내고, dats는 실제 숫자정보가 담겨있는 배열이다. (u4는 DWORD와 같다.) 자, 다음 함수는 bigint를 만들어주는 함수이다. u4 bigint_create(u4 len, bigint *xi) { xi->len=len; xi->dats=(u4*)malloc(len*sizeof(u4)); if(xi->dats==NULL)return 0; return len; } 다음 함수는 bigint를 지워주는 함수이다...

프로그래밍/Multi precision 2009. 3. 29. 00:47

Big Integer는 기본적인 자료형 int보다 훨씬 더 큰 정수를 저장하기 위한 자료형이다. 특별한 일 없으면 int64로 어지간한 수는 다 표현할 수 있지만, 때때로 매우 큰 수가 필요하다규. 가장 쉬운 구현 방법은 char배열을 사용해서 10진수로 각 자리수를 저장하는 것이다. n자리수를 저장하는데 n바이트가 필요하므로, n바이트로 표현할수 있는 수 범위는 0 ~ 10^n -1 이다. 그런데 이 방법은 매우 비효율적이다. 그래서 좀 더 효율적인 방법으로 DWORD배열을 사용(32비트 프로그램 기준)하는데, 각 DWORD마다 10진수로 숫자를 9자리씩 저장하는 것이다. DWORD가 대략 42억까지 포함할 수 있으므로, 최대 9자리씩저장 할수 있다. n바이트로 표현할수 있는 수 범위는 0 ~ 10^(..

프로그래밍/Multi precision 2009. 3. 29. 00:23

지금까지 3차원 물체를 원하는 위치에서 바라봤을때 2차원 모습으로 투사하는 방법에 대해 설명했다. 뷰 변환, 프로젝션 변환을 통해서 기본 모델에서 프로젝션 공간까지 변환했다. 그러나 제일 앞에 생략하고 넘어간게 있다. 기존의 모델을 확대하거나 축소하거나 회전하는 등의 변형을 해서 출력하고 싶다면? 각각의 모델별로 변환행렬이 필요하다. 이 변환을 월드 변환이라고 한다. 즉 모델은 다음과 같은 변환을 거친다. 기본 모델 ↓ 월드 변환(World Transformation): 모델을 변형한다. ↓ 월드 공간 ↓ 뷰 변환(View Transformation): 모델을 카메라의 관점에서 본 형태로 변형한다. ↓ 뷰 공간 ↓ 프로젝션 변환(Projection Transformation): 평면에 투사한다. ↓ 프로..

프로그래밍/3D 2008. 12. 30. 00:27

비둘기집의 원리란 다음과 같은 것이다. 비둘기가 n마리 있고, 비둘기집이 m개 있는데, n>m이면, 반드시 비둘기가 2마리 이상 들어가는 집이 하나 이상 있다. 예를 들어 비둘기 5마리가 비둘기 집 3개에 들어가려면 어떤 집에는 비둘기가 2마리 이상이 들어간다는 것이다. 비둘기집의 원리는 너무 당연한 사실이지만, 이산수학에서 꽤 중요한 위치를 차지하고 있는 놈이다. 위키백과에서 관련된 내용을 살펴볼수 있다: 위키백과-비둘기집의 원리 컴퓨터 압축기술에 비둘기집의 원리를 적용해보자. 데이터 압축이란 어떤 데이터를 인코딩의 과정을 거쳐 원래 크기보다 작은 데이터로 변형하고, 다시 디코딩 과정을 거쳐 원래 데이터를 복원해 내는 일 모두를 일컫는다. 데이터가 압축될때 원래 데이터의 크기보다 크기가 줄어드는데, 여..

프로그래밍 2008. 12. 25. 23:28

최대공약수를 구하는 알고리즘에는 대표적으로 유클리드 호제법이 있다. 유클리드 호제법을 간단히 설명하면 다음과 같다. 1. 두 수 a,b를 입력받는다. 2. a가 b보다 크면 a를 b로 나눈 나머지를 구한다. b가 a보다 크면 그 반대로 한다. 3. 나누어서 얻는 나머지를 새로운 a, 원래 a,b중 작은값을 b로 하고 2번으로 돌아간다. 4. 만약 a나 b가 0이 되었다면 이 때의 나머지 b나 a의 값이 최대공약수이다. 이 알고리즘은 a와 b의 최대공약수나 a-b와의 최대공약수나 같다는 사실을 이용해서 쉽게 증명할수 있다. int gcd(int a,int b) { if(b==0)return a; return gcd(a,a%b); } 위 코드는 유클리드 호제법을 간단하게 c코드로 짜본것이다. (단 a>=b일..

프로그래밍/테크닉 2008. 12. 20. 22:01

[C/C++] volatile 키워드 병맛사족 2008/12/20 03:09 volatile 키워드는 변수 등이 컴파일러에 의한 최적화에 의한 영향을 받지 않도록 하는 역할을 한다. 일반적인 초급 프로그래밍에서는 거의 쓸 일이 없지만, 후에 concurrent한 프로그램을 작성한다든지, 시스템의 로우 레벨을 건드리게 되는 경우에는 지나치게 똑똑한 컴파일러에 의한 예상치 못한 최적화로 인하여 곤란에 빠질 수가 있다. 예제를 위해 다음의 두 함수를 만들어 보았다. [CODE] 쓰레드로 돌릴 두 함수 int z; // z를 찍기만 하는 쓰레드 DWORD WINAPI thread_a( LPVOID ) { int i ; for( i = 0; i

프로그래밍 2008. 12. 20. 19:52

하아 어느덧 여러 수학함수를 구현해보려는 기나긴 장정이 역삼각함수에까지 이르렀다. 아직 쌍곡선 함수를 비롯한 여러 수학함수들이 남아있지만, 거의 쓰이지 않는 관계로(또한 귀찮은 관계로) 글쓰기를 무기한 연기해버리기로 했다. 역삼각함수는 각을 구해내기 위해서 자주 쓰인다. acos,asin,atan 등이 있지만, 가장 유용한 함수는 atan2이다. atan2는 x축 변위,y축 변위를 받아서 -Pi에서 Pi 사이의 각을 구해준다. (acos,asin,atan함수는 제한된 범위의 각만 구해낼수 있다.) 일단 atan2함수도 atan를 이용해 구현될수 있으므로 좀 뒤로 미루자. 먼저 역시 방대한 지식이 담겨있는 위키백과만큼 좋은 참조물도 없다. 영어위키백과: 역삼각함수 역삼각함수들에 대해서 다음 등식이 성립한다..

프로그래밍/테크닉 2008. 12. 8. 00:07

여태까지 제곱근함수와 지수함수, 로그함수를 대충 구현해보았다. 이를 이용하면 어지간한 계산들을 다 할 수 있으나, 한 가지 막히는 부분이 있으니 바로 삼각함수이다. 삼각함수는 약방의 감초라할만큼 안 들어가는 곳 없이 두루두루 들어간다. 삼각함수는 비용이 비싼 측에 낀다. (계산량을 줄일만한 획기적 방법이 별로 없는듯하다.) 그래서 삼각함수 연산을 자주 하는 프로그램에서는 대게 테이블을 만들어놓고 참조하는 방법을 쓴다. 이 방법이 대체로 빠른 방법이어서 추천하는 바이다. (가장 좋은 방법은 FPU의 빵빵한 지원이라고나 할까) 아래에 설명하는 계산법은 그냥 이렇게도 계산할수 있다는 거지, 이 식을 활용해서 계산하면 좋다는 의미는 아니다. 공학용으로 삼각함수계산을 어떻게 하나 궁금해서 영어위키백과를 찾아봤더니..

프로그래밍/테크닉 2008. 12. 7. 01:39