여기선 현재 사용중인 나눗셈 코드를 살펴보겠습니다.
현재. 11년 7월 11일. 사용중인 코드로
Matt씨의 코드를 제 상황에 맞게 약간만 고쳐서 사용하고있습니다.
자세히 설명하지 않겠습니다.
왜냐면.. 제가 별로 맘에 안들기 때문입니다.. -0-..
바꾸고 싶은데.. 하.. 맘에 안들긴 하는데..
잘 안떠오르네요.. 나중에 천천히 생각나면 바꾸겠습니다.
그 때는 자세히 써놓겠습니다.
현재. 11년 7월 11일. 사용중인 코드로
Matt씨의 코드를 제 상황에 맞게 약간만 고쳐서 사용하고있습니다.
자세히 설명하지 않겠습니다.
왜냐면.. 제가 별로 맘에 안들기 때문입니다.. -0-..
바꾸고 싶은데.. 하.. 맘에 안들긴 하는데..
잘 안떠오르네요.. 나중에 천천히 생각나면 바꾸겠습니다.
그 때는 자세히 써놓겠습니다.
void BigInteger::divideWithRemainder(const BigInteger &Divisor, BigInteger &Quotient) { /* * 제수가 피제수보다 큰 경우는 나눗셈을 할 필요가 없습니다. * 몫은 0, 나머지는 피제수가 될테니까요. * 연산을 하지 않아도 되기 때문에, 이와 같은 경우는 * 사전에 조건문으로 걸러주는것이 연산속도를 빠르게 해 줄수 있습니다. * 하지만 이 조건문에서 시간을 많이 잡아먹으면 안됩니다. * * 제수 > 피제수 를 판별할 수 있는 방법으로는 * 정확한 1가지와 대략적인 2가지 방법이 있습니다. * * 1. CompareTo함수를 사용하여 크기가 큰지 판별하기 * 제일 정확한 방법이지만, 오래 걸립니다. * 큰 숫자일 경우는 제수와 피제수의 크기가 같다면 * for문을 수백만번을 돌 수도 있습니다. * * 2. 제수와 피제수의 비트 길이 체크하기 * 비트 길이는 제일 높은 비트가 어디 있는지를 나타내는 것과 같습니다. * 따라서, 제일 높은 비트는 같지만 제수가 큰 경우는 제외하고 * ex) 피제수 : 10(2), 제수 : 11(3) * 나머지는 판별가능 합니다. * * 3. 제수와 피제수의 블럭 길이 비교 * 가장 빠른 방법입니다. 단순하게 제수와 피제수의 * len을 비교하는 것이기 때문입니다. * 하지만, 그만큼 놓치는 경우도 많습니다. * * 세 가지 방법으로 제수와 피제수의 크기를 비교할 수 있습니다. * 그 중, 가장 빠른 3번째 방법을 사용하겠습니다. * 다시 한번 말씀드리지만, 이 조건을 써주지 않아도 * 연산 과정을 통해 몫과 나머지를 구할 수 있습니다. * 다만 불필요한 연산 과정을 거치지 않기 위해서 * 걸러내는 것이므로 모든 경우에 대해서 * 그 경우를 살필 필요는 없습니다. */ if (blklength() < Divisor.blklength()) { Quotient = _Zero; return; } // 이제, (*this).len >= Divisor.len 이 성립합니다. /* * 나눗셈을 정의하는 데에는 의견이 갈립니다. * 양수와 양수의 나눗셈은 상관 없지만 * 양수와 음수, 음수와 음수의 나눗셈에서 구현한 사람마다 * 차이가 있습니다. * 이 부분은 컴파일러마다도 결과값이 달라진다고 합니다. * 표준이 정의되지 않았다고 하네요.. * --------------------------------- * 2 / (-3) = 0 2 % (-3) = 2 * --------------------------------- * 2 / (-3) = -1 2 % (-3) = -1 * --------------------------------- * * 2 / (-3)의 소수까지의 나눗셈을 구하면 * -0.66666666666666666666... 입니다. * 여기서 소수점을 버릴지.. * 아니면 올림 처리 할지에 따라 결과가 달라지는 것입니다. * 전, 위에 것을 토대로 만들겠습니다. * vc가 위와 같이 나오기 때문입니다. * 아래는 Matt씨가 만든것에서 저렇게 만듭니다. */ /* 전반적인 방법.. * 알고리즘은 초기의 알고리즘과 비슷합니다. * 초등학교 때, 배우던 나누기 방법을 그대로 사용합니다. * 초기와 다른 점은 좀 더 빠르다는 것입니다. * * (초기 나누기 알고리즘) * 776 * ---------- * 159 | 123456 * 111300 * ------ * 12156 * 11130 * ------- * 1026 * 954 * ------ * 72 * * * (현재 나누기 알고리즘) * 776 * ---------- * 159 | 123456 * 1113 * ------ * 1215 * 1113 * ------- * 1026 * 954 * ------ * 72 * * 두개의 차이점을 아시겠습니까? * 뺄셈 과정이 다릅니다. * 위에서는 123456 - 111300을 구한다면 * 아래에서는 1234 - 1113을 구합니다! * 큰 숫자라면 엄청난 속도차이가 아닐 수 없습니다!! */ index i, j, k; unsigned int i2; blocktype temp; bool borrowIn, borrowOut; BigInteger orig(*this); index origLen = len; // 계산상, *this.blk[len]을 접근해야 합니다. // 따라서, 오류를 막기위해 재할당 합니다. Reallocate(len + 1); memmove(blk, orig.blk, sizeof(blocktype) * origLen); // 빼기 값을 저장하기 위해 사용합니다. blocktype *subtractBuf = new blocktype[len]; memset(subtractBuf, 0, sizeof(blocktype) * len); // 몫을 미리 할당합니다. Quotient.Reallocate(origLen - Divisor.len + 1); // 위에서부터 비트 하나씩 계산해나갑니다. i = Quotient.len; while (i > 0) { i--; Quotient.blk[i] = 0; i2 = N; while (i2 > 0) { i2--; for (j = 0, k = i, borrowIn = false; j <= Divisor.len; j++, k++) { temp = blk[k] - Divisor.Get_LShiftedBlock(j, i2); borrowOut = (temp > blk[k]); if (borrowIn) { borrowOut |= (temp == 0); temp--; } subtractBuf[k] = temp; borrowIn = borrowOut; } for (; k < origLen && borrowIn; k++) { borrowIn = (blk[k] == 0); subtractBuf[k] = blk[k] - 1; } if (!borrowIn) { Quotient.blk[i] |= (blocktype(1) << i2); while (k > i) { k--; blk[k] = subtractBuf[k]; } } } } if (Quotient.len != 1 && Quotient.blk[Quotient.len - 1] == 0) Quotient.len--; ZapLeadingZeros(); delete [] subtractBuf; // 몫과 나머지의 부호지정 Quotient.sign = (sign == Divisor.sign) ? Positive : Negative; if (Quotient.len == 1 && Quotient.blk[0] == 0) Quotient.sign = Zero; if (len == 1 && blk[0] == 0) sign = Zero; }
'프로젝트 > 큰수 클래스(Big Numerics)' 카테고리의 다른 글
[BigInteger - 17] 문자열로 입력받기 (0) | 2011.07.14 |
---|---|
[BigInteger - 16] 문자열로 출력하기 (0) | 2011.07.12 |
[BigInteger - 15] 나눗셈(Part 2) (0) | 2011.07.09 |
[BigInteger - 14] 나눗셈(Part 1) (0) | 2011.07.08 |
[BigInteger - 13] 곱셈 (0) | 2011.07.08 |