高精度计算(四):大整数乘法(采用“万进制”)

时间:2021-09-03 03:34:45

【例1】大整数乘法。

      编写一个程序,求两个不超过200 位的非负整数的积。

      (1)编程思路。

      大整数乘大整数,实质就是在小学竖式乘法的基础上枚举各个乘数位与被乘数相乘,累加到结果当中。其中乘数中的第j位与被乘数中的第i位相乘时,结果应该保存到结果的第i+j-1位中。

      (2)源程序。

#include <iostream>
using namespace std;
const int base=10000;
const int maxlen=50+2;
void charTobignum(char *ch,int *bignum)
{
      int len,i,j,p,num;
      memset(bignum,0,sizeof(int)*maxlen);
      len=strlen(ch);
      bignum[0]=len%4==0?len/4:len/4+1;
      i=1;
      while (i<=len/4)
      {
          num=0;
          p=len-4*i;
          for(j=1;j<=4;j++)
              num=num*10+(ch[p++]-'0');
          bignum[i]=num;
          i++;
       }
       if (len%4!=0)
       {
            num=0;
            for (i=0;i<=len%4-1;i++)
                 num=num*10+(ch[i]-'0');
            bignum[len/4+1]=num;
        }
}
void printbignum(int *bignum)
{
       int *p=*bignum+bignum;
       cout<<*p--;
       cout.fill('0'); // 定义填充字符'0'
       while(p>bignum)  { cout.width(4); cout<<*p--; }
       cout<<endl;
}
void multiply( int *bignum1, int *bignum2, int *bignum_ans)
{
      int carry=0, i, j;
      memset(bignum_ans, 0, sizeof(int)*2*maxlen);
      for (j=1; j<=bignum2[0]; j++){
           for(i=1; i<=bignum1[0]; i++){
               bignum_ans[i+j-1]+=carry+bignum1[i]*bignum2[j];
               carry=bignum_ans[i+j-1]/base;
               bignum_ans[i+j-1]%=base;
            }
            i=j+bignum1[0];
            while(carry){
                 bignum_ans[i++]=carry%base;
                carry/=base;
            }
       }
       bignum_ans[0]=bignum1[0]+bignum2[0];
       while( !bignum_ans[*bignum_ans] ) --bignum_ans[0];
}
int main()
{
       int bignum1[maxlen],bignum2[maxlen],bignum_result[2*maxlen];
      char numstr[maxlen];
      cout<<"请输入第1个大整数:";
      cin>>numstr;  
      charTobignum(numstr,bignum1);
      cout<<"请输入第2个大整数:";
      cin>>numstr;
      charTobignum(numstr,bignum2);
      multiply(bignum1,bignum2,bignum_result);
      cout<<"两个大整数的积是 :";
      printbignum(bignum_result);
      return 0;
}

      将上面源程序中的输入输出提示语句删除后,提交给POJ 2389 “Bull Math”,可以Accepted。