여기선 현재 사용중인 나눗셈 코드를 살펴보겠습니다.
현재. 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;
}
Posted by 투명테잎