나의 큰 O는 log x야

bigint값을 10진수로 입력받기 위해서는 10진수를 2진수로 변환해야하는데, 이는 앞에서 다루었던 시프트 더하기 3 알고리즘을 거꾸로 작동시키면 된다. 32비트에 최적화하기 위해 시프트 더하기 1647483648 알고리즘을 거꾸로 작동시켜보자. 시프트 더하기 1647483648 알고리즘에서는 자릿수가 500000000 이상인 자리에 1647483648를 더해주고 전체 수를 1비트 왼쪽으로 시프트했다. 그러므로 얘를 거꾸로 뒤집으면 전체 수를 오른쪽으로 1비트 시프트하고, 자릿수가 2147483648 이상인 자리에 1647483648를 빼주면 된다. 즉, 우리가 짤 함수를 정리하면 다음 정도가 되겠다. 10진수를 9자리씩 쪼갠다. 각각의 덩어리를 한 배열에 넣고, 시프트 더하기 1647483648 역 ..

프로그래밍/Multi precision 2009. 4. 30. 15:52

바로 전 글에서 알고리즘에 대해 주절주절 설명하느라고 코드를 올리지 못했다. 시프트 더하기 16..(몇이었더라)알고리즘을 쓰도록 하겠다. 그전에 먼저 bigint의 길이를 줄여주는 함수를 작성한다. u4 bigint_shrink_i(bigint *dest) { u4 dlen=dest->len; for(u4 i=dest->len;i>0;i--) { if(dest->dats[i-1]==0)dest->len--; else break; } return dlen; } 이 함수는 bigint의 현재 길이에서 필요없는 부분(예를 들어 0000001101101011011에서 앞의 0000000 같은놈)을 잘라내어서 길이를 줄인다. 그리고 원래 길이를 리턴한다. 이 함수를 만든 이유는 계산시에 불필요한 부분을 계산하지 ..

프로그래밍/Multi precision 2009. 4. 26. 02:47

지금까지 정말 bigint를 정의하고 사칙연산들을 수행하는 함수를 짜보았다. 근데 아무리 계산하면 뭐하나 눈에 보이지가 않는걸! 드디어 BigInteger 구현은 막바지에 다다랐다. 10진수 입출력만 끝내면 이제 아무리 큰 수를 계산하는 것도 두렵지 않다. 컴퓨터는 내부적으로 2진수로 수를 저장한다. 따라서 2진수를 10진수로 보여주려면 변환 과정이 필요하다. 2진수를 10진수로 변환하는 가장 쉬운 방법은 10으로 나누어서 나머지를 차례로 취하는 것이다. n을 10진수로 출력하기(Psuedo코드) 방법1-1. 10으로 나누기. print_dec(n) { print_dec(n/10) print(n%10) } 이 방법은 간단하고 이해하기 쉬울지는 몰라도 log_10(n)번의 나눗셈과 재귀호출이 필요하다. 방..

프로그래밍/Multi precision 2009. 4. 26. 02:26

초등학생 때 배웠던 나눗셈의 알고리즘이다. big integer 나눗셈에서도 이 알고리즘을 그대로 쓴다. void bigint_div_i(bigint *rmd, bigint *quo, const bigint *divisor) { memset(quo->dats, 0, quo->len*sizeof(u4)); u4 ns=bigint_bits(rmd); u4 ms=bigint_bits(divisor); if(ns=0;--i) { if(bigint_gte_i(rmd, &temp)) { bigint_sub(rmd, &temp); quo->dats[i>>5]|=116) { src=src>>16; b+=16; } if(src>>8) { src=src>>8; b+=8; } if(src>>4) { src=src>>4; b..

프로그래밍/Multi precision 2009. 4. 25. 03:29

예전에 bigint가 0보다 큰지 작은지 같은지를 비교하는 bigint_sign함수를 만든적이 있다. 두 bigint의 대소를 비교하기 위해 빼고 부호를 확인해도 되지만, 그것보다 효율적인 방법으로 두 bigint의 대소를 비교하는 함수를 만들어보자. 그 전에 먼저 bigint가 몇자리 수인지 계산하는 함수를 만든다. u4 bigint_size_i(const bigint *src) { for(u4 i=src->len-1;(long)i>=0;--i) { if(src->dats[i]==0)continue; return i+1; } return 0; } 특별한 알고리즘 같은것은 없고, 최고자리수부터 차례대로 내려오면서 처음으로 0이 아닌 숫자가 나올때의 자릿수를 돌려준다. 이제 두 bigint가 같은지 확인하..

프로그래밍/Multi precision 2009. 4. 21. 00:54

시프트란것은 전체 비트배열을 왼쪽으로 또는 오른쪽으로 밀어주는 것을 말한다. n비트 왼쪽으로 시프트하는 것은 2^n을 곱하는 것, 오른쪽으로 시프트하는 것은 2^n을 나누는것과 같은 효과를 나타낸다. a[4] a[3] a[2] a[1] a[0] dats[0]=dest->dats[shiftb]>>src; for(u4 i=1;ilen-shiftb;++i) { dest->dats[i-1]|=dest->dats[i+shiftb]dats[i+shiftb]>>src; } memset(dest->dats-shiftb, 0, shiftb*sizeof(u4)); } 먼저 오른쪽으로 src비트만큼 시프트하는 함수다. 특별한 건 없고, u4가 32비트이므로, 32로 나누어서 몫만큼은 배열 전체를 밀어주고, 나머지만큼만 오른..

프로그래밍/Multi precision 2009. 4. 12. 15:12

두 u4배열의 곱셈은 다음과 같이 한다. a[2] a[1] a[0] X b[1] b[0] --------------------------------------------------------------------------------------- a[2]*b[0] a[1]*b[0] a[0]*b[0] a[2]*b[1] a[1]*b[1] a[0]*b[1] 두 수의 곱셈을 하듯이 두 u4배열을 곱해주면 된다. 이 때 u4*u4는 최대 약 2^64 까지 나올수 있으므로 일반적인 int형에는 저장할 수가 없다. 따라서 64비트 int의 부호없는 타입을 u8이라고 정의하고, u8로 받아야 한다. 먼저 bigint의 부호없는 곱셈을 하는 함수를 만든다. void bigint_mul_i(bigint *dest, con..

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

bigint에서 음수는 2의 보수 표기법을 사용하도록 한다. 그것이 덧셈 뺄셈에 간편하기 때문. 다음 함수는 2의 보수를 취해주는 함수이다. 즉 부호를 바꿔주는 함수. void bigint_neg(bigint *dest) { for(u4 i=0;ilen;++i) { dest->dats[i]=~dest->dats[i]; } add_u4(dest->len, dest->dats,1); } u4 bigint_createnegcopy(bigint *xi, const bigint *src) { xi->len=src->len; xi->dats=(u4*)malloc(xi->len*sizeof(u4)); if(xi->dats==NULL)return 0; for(size_t i=0;ilen;i++) { xi->dats[i..

프로그래밍/Multi precision 2009. 3. 29. 01:13