나의 큰 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

흔히 빅 인터거(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