大數相加/大數相乘

有人要的

// 大數相加/大數相乘 2007/5/14 0:54:49,14 21:20-23:51

//g++ -pipe -o add add.cpp && add



#include <iostream>

#include <cstring>

//using namespace std;



const int debug=0;



const int MAX_NUMBERS_COUNT=10;

const int MAX_DIGITS=256;

const char* DigitChar="0123456789abcdefghijklmnopqrstuvwxyz";

 //="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";



int MapDigitCharToNumber(char& c, const int& base){

 const char* p=DigitChar;

 while(*p&&c!=*p)p++;

 if(debug>0)std::cout<<"MapDigitCharToNumber: ["<<c<<"] -> "<<(p-DigitChar)<<"("<<*p<<")"<<std::endl;

 if(*p==NULL||p-DigitChar>=base){

  std::cout<<"Illegal digit: ["<<c<<"] -> 0"<<std::endl;

  c=DigitChar[0];

  return 0;

 }

 return p-DigitChar;

}





void regularByBase(int* n, int base, int max_digits){

 int i=0,tr=0;

 int* ptr=n;

 for(;i<max_digits;i++){

  if(debug>0)std::cout<<"regularByBase: ["<<(ptr-n)<<"]"<<tr<<"+"<<*ptr<<" -> ";

  tr+=*ptr;

  *ptr++=tr%base;

  if(debug>0)std::cout<<*ptr<<std::endl;

  tr/=base;

 }

}



void doMultiplication(int result[], const int* num, int& max_d, const int& base=8){

 int i=0,num2[MAX_NUMBERS_COUNT*MAX_DIGITS]={0};//num2[sizeof(result)/sizeof(int)]={0};

 if(debug>0)std::cout<<"doMultiplication: base="<<base<<std::endl;

 for(;i<max_d;i++){

  for(int j=0;j<max_d;j++){

   if(debug>0)std::cout<<result[i]<<" * "<<num[j]<<" -> ["<<(i+j)<<"] "<<num2[i+j];

   num2[i+j]+=result[i]*num[j];

   if(debug>0)std::cout<<" => "<<num2[i+j];

   if(base>0&&num2[i+j]>base) // may cause error if not execute!

    num2[i+j+1]+=num2[i+j]/base,num2[i+j]%=base;

   if(debug>0)std::cout<<" => "<<num2[i+j+1]<<" , "<<num2[i+j]<<std::endl;

  }

 }



 max_d*=2;

 if(base>0){

  while(num2[--max_d]==0);

  regularByBase(num2,base,++max_d);

 }

 if(debug>0){

  std::cout<<"doMultiplication: max digits="<<max_d<<std::endl;

  std::cout<<"doMultiplication: ("<<base<<")";

  for(int j=max_d;j>=0;j--)

   std::cout<<num2[j];

  std::cout<<std::endl;

 }



 for(i=max_d;i>=0;i--)

  result[i]=num2[i];

}





int main(){



 int base; // base to use



 std::cout<<"Please input base (2~16): ";

 std::cin>>base;

 if(base<2||base>16)return 0;



 int computeMethod;

 std::cout<<"Please input the compute method (0: addition, others: multiplication): ";

 std::cin>>computeMethod;





 char input_num[MAX_NUMBERS_COUNT][MAX_DIGITS]={{0}}; // numbers inputted

 int num_array[MAX_NUMBERS_COUNT][MAX_DIGITS]={{0}}; // number array

 int i,max_d=0; // loop index, max digits



 // input numbers & put reversed digits into num_array

 for(i=0;i<MAX_NUMBERS_COUNT;i++){

  std::cout<<"Please input a number "<<i<<" (e.g. 101, input 0 to begin compute): ";

  std::cin>>input_num[i]; // need to check if overflow

  int l=strlen(input_num[i]),d=0; // length of number, the digit processing to

  if(l==0||l==1&&MapDigitCharToNumber(input_num[i][0],base)==0)break;

  if(max_d<l)max_d=l;

  while(l>0)

   num_array[i][d++]=MapDigitCharToNumber(input_num[i][--l],base);

 }

 if(i<2)return 0;



 int inC=i; // count of input numbers

 int* r=new int[inC*MAX_DIGITS]; // result number

 //int r[inC*MAX_DIGITS]={0}; // result number



/*

 int a[]={4,2,3,4,5,6,7,8,9,3};

 i=sizeof(a)/sizeof(int);

 while(i>0)n1[p1++]=a[--i];



 int b[]={9,0,1,2,3,4,5,6,7,8};

 i=sizeof(b)/sizeof(int);

 while(i>0)n2[p2++]=b[--i];

*/





 if(debug>0)std::cout<<"max digits: "<<max_d<<std::endl;





 if(computeMethod){

  // multiplication

  for(i=0;i<max_d;i++)

   r[i]=num_array[0][i];



  for(i=1;i<inC;i++)

   doMultiplication(r,num_array[i],max_d,base);



 }else{

  // addition

  //int carry=0;

  for(i=0;i<max_d/*||carry>0*/;i++){

   int j=0,tr=0; // loop index, temp result

   for(;j<inC;j++){

    if(debug>0)std::cout<<" + "<<num_array[j][i];

    tr+=num_array[j][i];

   }

   if(debug>0)std::cout<<std::endl;

   r[i]=tr;

/* 數字量小時可不用

   carry+=tr;

   r[i]=carry%base;

   carry/=base;

*/

  }



 }



 regularByBase(r,base,max_d);



 // print result

 std::cout<<std::endl<<input_num[0];

 for(i=1;i<inC;i++)

  std::cout<<(computeMethod?" * ":" + ")<<input_num[i];

 std::cout<<" = "<<std::endl;



 i=MAX_DIGITS;

 while(r[--i]==0);

 while(i>=0)

  std::cout<<DigitChar[r[i--]];



 std::cout<<std::endl;



 return 0;

}