나의 큰 O는 log x야

(짤방은 그냥 재미로...) BigFloat에서 덧셈과 뺄셈을 구현하기 위해서는 초등학교 다닐때의 마음으로 되돌아가서, 컴퓨터에게 받아올림과 받아내림을 알려줘야합니다.ㅋ (p = 2^32) c2 = (a2 + b2)를 p로 나눈 나머지 c1 = (a1 + b1 + 받아올림)을 p로 나눈 나머지 c0 = (a0 + b0 + 받아올림)을 p로 나눈 나머지 이런식으로 계산이 되지요. 다행히도 우리는 구현할때 a_n + b_n을 2^32으로 매번 나눠줄 필요가 없습니다. 32비트 CPU에서는 2^32를 넘어가는 숫자는 자동으로 오버플로우되어 버리기 때문이지요. 그러면 받아올림이 일어났는지는 어떻게 알수 있을까요? 실제로 CPU 어셈블리 상에서는 add연산에서 오버플로우가 발생하면, 캐리플래그(CF)가 세트되어서..

프로그래밍/Multi precision 2012. 10. 16. 01:51

기초적인 BigFloat의 수학적 원리는 다음과 같아요~ 십진법은 위와 같은 규칙으로 표현됩니다. 십진법에서의 덧셈은 각 자리수에 해당하는 숫자들끼리 더해서 받아올림을 함으로써 연산됩니다. 이를 32비트 컴퓨터에서 효율적으로 구현하기 위해서는 10진법보다는진법을 사용하는것이 좋겠지요. 이런 모양으로 실수를 표현할수 있을겁니다. 일단 이번 연재의 궁극적인 목표는 Pi값의 계산이니만큼 정수부분이 무지막지하게 큰 정수를 표현해야할 필요는 없습니다. a, b부분은 쳐내고, 다음과 같은 모양으로 표현하는게 괜찮겠네요. a0은 정수부분을 표현하는 데이터로, a1부터는 소수점 이하를 표현하는 데이터로 활용하면 될것입니다. 자 이제 이걸 바탕으로 우리의 BigFloat자료형이 될 RealReal구조체를 짜봅시다. ty..

프로그래밍/Multi precision 2012. 10. 16. 00:45

c/c++로 코딩하다 보면 매우 간결한 조건문이 필요할 때가 있다. (예를 들어 인수가 잘못되어서 에러값을 리턴하는 경우처럼) 이럴 때는 {}를 사용하지 않고 한 줄 짜리 if문을 만드는 경우가 있다. 그런데 가끔씩 한 줄 짜리 if문에 두 가지 명령을 쑤셔넣으려고 다음과 같이 한다. if(cond)a++,b++; 이는 아무 문제가 없다. 하지만 다음과 같은 경우는 문제가 발생한다. if(error)free(ptr),return -1; (아마 에러가 발생해서 그 전에 할당해놓은 메모리를 해제하고 리턴을 하는 모양이다.) 결국 다음과 같이 코드를 고치게 된다. if(error) { free(ptr); return -1; } 왜 위의 경우는 되는데 아래의 경우는 안될까? 이는 c의 쉼표 연산자(,)를 잘못 ..

프로그래밍/테크닉 2009. 9. 13. 23:14

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