アルゴリズム設計と分析:第三章分治3.3バイナリ大整数の乗算

/*
         :
          ，      n             

 x = 3141, A = 31 B=41
  y = 5327,	C = 53,D=27
  x*y = AC*2^n + (AD + BC)*2^(n/2) + BD
      = AC*2^n + ((A-B)*(D-C) + A*C + B*D)*2^n + BD //      

   :          

              
  :
3141 5327 10（          ）
9 11 2(                      )

  :
16732107
99
731074749


*/

/*
          ，        ,     x,y   10      
*/

#include <stdio.h>
#include <iostream>

using namespace std;
bool g_valid;//      

int sign(int a)//    a   
{
	return a > 0 ? 1 : -1;
}

int myAbs(int a)
{
	return a > 0 ? a : -1*a;
}

int digitCount(int a,int iBase)
{
	int iTotalDigit = 0;
	do
	{
		a /= iBase;//     
		iTotalDigit++;
	}while(a);
	return iTotalDigit;
}

int getBack(int a,int iBase,int iTotalDigit)//iBase   
{
	if(a <= 0)//      a   
	{
		g_valid = false;
		return -1;
	}

	/*           ，        。            。1234：        /2,        ，
	                 ，      。
	       ，           ，    ，                     
	*/
	int iCnt = 0;
	int iSum = 0;
	int iFactor = 1;
	do
	{
		iSum += iFactor*(a % iBase);
		iFactor *= iBase;
		a /= iBase;
		iCnt++;
		if(iCnt == iTotalDigit/2)
		{
			break;
		}
	}while(a);
	return iSum;
}

//  iBase^iExp
int myPow(int iBase,int iExp)
{
	if(iExp == 1)//    
	{
		return iBase;
	}
	int iRet = myPow(iBase,iExp/2);
	iRet *= iRet;
	if(iExp % 2 == 1)
	{
		iRet *= iBase;
	}
	return iRet;
}

int multiply(int x,int y,int iBase)
{
	//     
	int iSign = sign(x) * sign(y);
	x = myAbs(x);
	y = myAbs(y);

	//   
	int iTotalDigitX = digitCount(x,iBase);
	int iTotalDigitY = digitCount(y,iBase);

	//
	if(iTotalDigitX != iTotalDigitY)
	{
		g_valid = false;
		return -1;
	}

	//    ，    1，       
	if(x == 1 && y == 1)
	{
		return iSign;
	}
	else
	{
		//                
		int iDivideNum = myPow(iBase,iTotalDigitX/2);
		int iBackX = getBack(x,iBase,iTotalDigitX);

		//     ，  5341     5300,    100
		int iFrontX = ( x - iBackX ) / iDivideNum;
		int iBackY = getBack(y,iBase,iTotalDigitY);
		int iFrontY = ( y - iBackY ) / iDivideNum;

		//        
		int iM1 = iFrontX * iFrontY;
		int iM2 = iBackX * iBackY;
		int iM3 = (iFrontX - iBackX) * (iBackY - iFrontY) + iM1 + iM2;

		int iRet = iSign * ( iM1*myPow(iBase,iTotalDigitX) + iM3*myPow(iBase,iTotalDigitX/2) + iM2 ); 
		return iRet;
	}
}

void process()
{
	int x,y,iBase;
	while(EOF != scanf("%d %d %d",&x,&y,&iBase))
	{
		g_valid = true;
		int iRet = multiply(x,y,iBase);
		if(g_valid)
		{
			printf("%d
",iRet);
		}
		else
		{
			printf("        %d %d      ，   !
",x,y);
		}
	}
}

int main(int argc,char* argv[])
{
	process();
	getchar();
	return 0;
}