[BigInteger - 13] 곱셈

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

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;
}