투 명 테 잎

나누기 함수는 기본적으로
몫과 나머지를 동시에 구할 수 있습니다.
나머지->divideWithRemainder(나누는 수, 몫); 
같은 형태로 사용하기 때문입니다.

/, % 연산자 오버로딩 함수는 초기나 지금이나 변화가 없기 때문에 뒤에서 언급하겠습니다.

초기 나누기 알고리즘을 간략하게 설명하면..

1. 초등학교 때 배웠던 사용하던 방식을 사용합니다.
2. 쉬프트 함수와 빼기 함수를 이용해 나누기를 진행합니다.

3. 예..(2진수의 나눗셈입니다.)
피제수 = 1 0010 1010 (298)을 제수 = 1100 (12)로 나누어 보겠습니다.

ㄱ. 피제수의 비트수는 9
ㄴ. 제수의 비트수는 4
ㄷ. 몫이 될 수있는 최고 자릿수는 9(피제수비트수) - 4(제수비트수) = 5(i)번째부터 가능
ㄹ. 제수를 왼쪽으로 5(i)쉬프트, 1100 << 5(i) = 110000000
ㅁ. 피제수와 제수를 비교
      1. 피제수가 크거나, 같으면
            ㄱ. 피제수에다가 제수만큼을 빼준다.
            ㄴ. 몫의 낮은자리부터 i번째 비트가 1이된다.
ㅂ. 제수를 오른쪽으로 한칸 쉬프트
ㅅ. i가 0인지 비교
     1. 0이면 ㅁ.~ㅅ. for문 완료!
     2. 0이 아니면 i를 1감소시키고, ㅁ.으로 돌아가기 
ㅇ. 몫과 나머지의 부호를 구한다.
ㅈ. 몫은 zapLeadingZeros함수를 호출한다.(나머지는 뺄셈함수내에서 호출하므로 할 필요 없다.)

ㄱ. ~ ㅈ. 까지가 알고리즘의 전체입니다.
저렇게 하면 298과 12의 나눗셈을 하게 되고
몫과 나머지가 각각 함수의 두번째 인수, 함수를 호출한 변수에 저장됩니다.

이것을 코드로 구현하면 다음과 같습니다.

void BigInteger::divideWithRemainder(const BigInteger &Divisor, BigInteger &Quotient)
{
	length Divided_BitLen, Dividor_BitLen;
	Divided_BitLen = bitlength(); // 피제수(나누어지는 수)의 비트길이
	Dividor_BitLen = Divisor.bitlength(); // 제수(나누는 수)의 비트길이

	// 제수의 비트길이가 더 길면
	// 연산을 할 필요 없습니다.
	// 몫은 0, 나머지는 *this가 됩니다.
	if (Divided_BitLen < Dividor_BitLen)
	{
		Quotient = _Zero;
		return;
	}

	/*
	* 나눗셈도 초등학교때 배운방법을 적용합니다.
	*
	*				      776
	*				----------
	*			159 |  123456
	*                  111300
	*                 ------
	*                   12156
	*                   11130
	*                  -------
	*                    1026
	*                     954
	*                   ------
	*                      72
	*/

	// 몫의 최대 가능한 길이만큼 재할당합니다.
	// 피제수가 n비트, 제수가 m비트라면
	// 몫의 최대 가능 비트는 n - m비트 입니다.
	// 블럭의 개수로 표현하면 (n - m)/32 + 1 입니다.
	Quotient.Reallocate( (Divided_BitLen - Dividor_BitLen)/N + 1 );

	// const BigInteger & 형으로 받은 제수를 변경을 위해 temp에 저장합니다.
	BigInteger temp(Divisor);
	
	// 몫이 위치할 수 있는 제일 높은 자리는 i
	length i = (Divided_BitLen - Dividor_BitLen);
	temp <<= i;
	// i자리부터 한자리씩 낮춰가며
	// *this에서 temp를 뺄 수 있는지 확인한다.
	do
	{/
		if (CompareTo(temp) != Less)// *this >= temp 라면..
		{
			// *this의 크기에서 temp의 크기만큼 뺌
			subtract(*this, temp);
			// 몫의 i번째 자리가 1이 된다.
			Quotient.blk[i >> 5] |= blocktype(1) << ( i & 31);
		}
		// temp를 오른쪽으로 한칸 쉬프트
		temp >>= 1;
	}while (i-- > 0); // i부터 0까지 계속 반복

	Quotient.ZapLeadingZeros();
	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;
}

나누기 부분이 제일 오래 걸렸습니다.
뭐.. 어떻게 해야할지를 모르니.. 오래 걸린것이겠죠.. 

Matt씨의 나누기 함수를 처음 봤을 때,
무슨 소리인지 하나도 몰랐습니다..
'진짜 이렇게 하면 나누기가 되는건가!?'
라고 생각했었죠..

그래서 다른 자료를 참고하여 다르게 만들었습니다!
물론 작동도 잘됬구요.
그러다.. BigInteger형을 다 만들어갈 무렵..
문득.. '내가 만든건 빠를까??'라는 생각이 들었습니다.

그래서 몇가지 테스트 코드를 만든 후, Matt씨가 만든것과
제가 만든것의 속도를 비교해보았습니다..
그. 런. 데..
하.. 정말.. 1g의 거짓없이..
똑같은 테스트코드를 도는데 50배 느렸습니다.. ㅋㅋㅋ
새로 만든 의미가 없었습니다.
엄청 허탈했지요..
테스트 한 부분은 출력 부분이였습니다.
(미리 말하자면, 저나 Matt것이나
나누기 함수가 출력 함수에서 메인역할을 하기 때문에,
출력 속도에 많은 영향을 미칩니다.)

출력 부분을 조금 손바줬더니.. 두배 빨라져서 25배 느려졌습니다..
이러면 안될것 같아서 출력 함수를 대대적으로 바껐습니다.
1자리씩 출력하게 하던걸 9자리씩 출력하게 만들었습니다.
그러니 9배 빨라졌습니다. 이 때, 재보니 4~5배 정도 느렸습니다.
더 이상 출력 부분에서 바꿀 부분이 안보였습니다.
숫자 출력 방법의 기본방향을 바꾸지 않는 이상 더이상의 진전은 보이지 않았습니다.
포기하고 그냥 여기서 만족할려던 찰나!!!!
'나누기 알고리즘을 바꿔볼까?'
'빨라질려나...?'라는 호기심반 절망감반으로 divideWithRemainder함수만 바꿔보았습니다.
헐 !!!!!!!!!!!!!!!!
엄청 빠르더만요..ㅋㅋㅋ
이제는 제것이 무려 7~8배 정도 빠르게 출력하는 것이였습니다!!
그래서 현재 Matt씨의 방법을 그래도 사용하고 있습니다.

나눗셈 부분은 두 부분으로 나누어
처음 제가 생각했던 알고리즘과
Matt씨의 알고리즘 두개를 모두 설명드리는 식으로 하겠습니다.
(글 쓰고 있는 지금도 Matt씨것의 원리를 모릅니다. 얼핏보니 같은 알고리즘이지만,
그 방법에서 많은 차이가 있는것 같습니다.) 

사칙연산 중에서 곱셈이 제일 쉽습니다.
방법도 우리가 흔히 쓰는 방식으로 곱셈을 하며
처리해야할 경우의 수도 덧셈, 뺄셈에 비해 훨씬 적습니다. ^^
쉬운 만큼
주석만으로도 충분히 쉽게 이해하실 수 있습니다.

multiply함수는 두 수의 크기의 곱셈을 연산 리턴하며
* 오버로딩 함수에서 부호를 고려합니다.

multiply함수입니다.

void BigInteger::multiply(const BigInteger &Left, const BigInteger &Right)
{
	// 두 수의 크기를 곱하여 this에 저장하는 함수입니다.

	// n자리 * m자리 곱셈 결과는 최대 (n+m)자리가 됩니다.
	Reallocate(Left.len + Right.len);

	// 두 32비트의 연산으로는 최대 64비트가 나옵니다.
	// 따라서, 두 블록의 연산값을 저장하기 위해
	// unsigned __int64형으로 임시 저장 변수를 만듭니다.
	unsigned __int64 temp_res;
	// 임시 저장값을 블록에 넣기 위해서는 64비트를
	// 다시 32비트씩 나누어 줘야합니다.
	blocktype blk_temp[2] = {0,};
	/*
	 * 곱셈 알고리즘은 초등학교떄 배우는 방식을 사용하였습니다.
	 * 대신 한자리씩 계산하는게 아닌 32비트씩 계산하는 것뿐입니다.
	 * 인터넷에서 이런 방식을 'Schoolbook Multiplication' 이라고 하네요.
	 * Google에서 Fast Multiplication을 치면 많은 자료가 나옵니다.
	 */
	index i,j,k,l;
	for(i = 0; i < Left.len; i++){
		temp_res = 0;
		for(j = 0; j < Right.len; j++){
			// 두 블럭을 곱하여 32비트씩 쪼개어 저장합니다.
			temp_res = unsigned __int64(Left.blk[i]) * Right.blk[j];
			blk_temp[0] = blocktype(temp_res);
			blk_temp[1] = blocktype(temp_res >> N);

			for (k = i + j, l = 0; l < 2; l++)
			{
				blk[k] += blk_temp[l];
				// 더했는데 blk[k]에서 자리 올림이 발생한다면!!!
				if (blk[k] < blk_temp[l])
				{
					// 연쇄 자리올림의 경우도 생각하여
					// 연쇄 자리올림이 발생하지 않을 때까지
					// 다음 자리들을 1 증가시킨다.
					for (;;)
					{
						blk[++k]++;
						if (blk[k] == 0)
							continue;
						else
							break;
					}
				}
				// blk_temp[0]에 대한 계산 후,
				// blk_temp[1]의 연산을 위해, k 재정의
				k = i + j + 1;
			}
		}
	}

	// len의 길이는 '최대' Left.len + Right.len이 될 수 있지만
	// Left.len + Right.len - 1도 될 수 있다.
	if (blk[len - 1] == 0)
		len--;
}

쉽죠~~? ^^
바로 이어서 * 오버로딩 함수입니다.

const BigInteger BigInteger::operator *(const BigInteger &x) const
{
	BigInteger temp;
	// 두 수중 0이 있으면 곱하나마나 0입니다.
	if (sign == Zero || x.sign == Zero)
		return temp;
	temp.multiply(*this, x);
	// 두 수의 부호가 같으면 +, 다르면 -가 됩니다.
	temp.sign = (sign == x.sign) ? Positive : Negative;
	return temp;
}