高精度计算（二）：大整数乘法

深碍√TFBOYSˉ_ 2023-03-13 05:07 28阅读 0赞

【例1】两个大整数乘法。

输入两个不超过200位的非负大整数a和b，求a×b的值。

（1）编程思路。

用 unsigned num1\[200\]和num2\[200\]分别存放两个乘数，用result\[400\]来存放积。计算的中间结果也都存在result 中。result 长度取400 是因为两个200 位的数相乘，积最多会有400 位。num1\[0\], num2\[0\], result\[0\]都表示个位。

计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将  
进位问题留待最后统一处理。

图1给出了753×68的计算过程。描述如下：

![format_png][]

1）先依次计算753的各位数字与8的乘积，并加到result数组的相应单元中。result数组的全部元素的初始值均为0。

2）再依次计算753的各位数字与6的乘积，并加到result数组的相应单元中。

3）乘法过程完毕。从 result\[0\]开始向高位逐位处理进位问题。result\[0\]留下4，

把2 加到result\[1\]上，result\[1\]变为60 后，应留下0，把6 加到result\[2\]上……最终使  
得result 里的每个元素都是1 位数，结果就算出来了。

在乘法过程中，num1的第i 位和num2的第j 位相乘所得的数，一定是要累加到  
result的第i+j 位上。这里i, j 都是从右往左，从0 开始数。

（2）源程序。

\#include <stdio.h>  
\#include <string.h>  
\#define MAX\_LEN 201  
void bigNumMul(char a\[\],char b\[\],char c\[\])  
\{  
      int i,j,n1,n2;  
      int num1\[MAX\_LEN\]=\{0\},num2\[MAX\_LEN\]=\{0\},result\[2\*MAX\_LEN\]=\{0\};  
      // 将a和b中存储的字符串形式的整数转换到num1和num2中去，  
      // num1\[0\]对应于个位、num1\[1\]对应于十位、……  
      n1 = strlen(a);  
      j = 0;  
     for (i = n1 - 1;i >= 0 ; i --)  
        num1\[j++\] = a * - '0';  
     n2 = strlen(b);  
     j = 0;  
    for (i = n2 - 1;i >= 0 ; i --)  
        num2\[j++\] = b - '0';  
    for (i=0;i < n2; i++ )  
    \{  
        for (j=0; j<n1; j++)  
            result\[i+j\] += num2\*num1\[j\];   // 两数第i, j 位相乘，累加到结果的第i+j 位  
    \}  
     //  统一处理进位问题  
    for( i = 0; i < MAX\_LEN \* 2; i ++ ) \{  
         if (result >= 10)  
         \{  
              result\[i+1\] += result / 10;  
              result %= 10;  
         \}  
    \}  
    bool isBeginZero = false;  
    j=0;  
    for (i=n1+n2-1; i>=0; i--)  
         if (isBeginZero)  
            c\[j++\]=result\+'0';  
        else if (result!=0)  
        \{  
             c\[j++\]=result\+'0';  
              isBeginZero = true;  
         \}  
    if (!isBeginZero) c\[j++\]='0';  
    c\[j\]='\\0';  
\}  
int main()  
\{  
     char a\[MAX\_LEN\],b\[MAX\_LEN\],c\[2\*MAX\_LEN\];  
     scanf("%s",a);  
     scanf("%s",b);  
     bigNumMul(a,b,c);  
     printf("%s\\n",c);  
     return 0;  
\}*

*（3）问题扩展。*

*下面我们来讨论如何完成一个大整数a和一个int型整型变量b的相乘。*

*图2给出了753×68的另一种计算过程。描述如下：*

*      *

*![format_png 1][]*

*       1）先依次计算753的各位数字与68的乘积，并存入到result数组的相应单元中。*

*       2）乘法过程完毕。从 result\[0\]开始向高位逐位处理进位问题。result\[0\]留下4，*

*把20 加到result\[1\]上，result\[1\]变为360 后，应留下0，把36 加到result\[2\]上……最终使  
得result 里的每个元素都是1 位数，结果就算出来了。*

*按这个思路可以实现一个大整数与int型整型变量相乘。源程序如下：*

*\#include <stdio.h>  
\#include <string.h>  
\#define MAX\_LEN 201  
void bigNumMul(char a\[\],int b,char c\[\])  
\{  
      int i,j,n1,n2,t;  
      int num\[MAX\_LEN\]=\{0\},result\[MAX\_LEN+10\]=\{0\};  
      // 将a和b中存储的字符串形式的整数转换到num1和num2中去，  
      // num1\[0\]对应于个位、num1\[1\]对应于十位、……  
      n1 = strlen(a);  
      j = 0;  
      for (i = n1 - 1;i >= 0 ; i --)  
         num\[j++\] = a - '0';  
      n2 =0;  
      t=b;  
      do \{  
           n2++;  
           t=t/10;  
       \} while (t!=0);  
       for (i=0;i < n1; i++)  
            result = num\*b;  
       //   统一处理进位问题  
       for (i = 0; i < n1+n2; i++)  
       \{  
            if (result >= 10)  
           \{  
                result\[i+1\] += result / 10;  
                result %= 10;  
            \}  
       \}  
      bool isBeginZero = false;  
      j=0;  
      for (i=n1+n2-1; i>=0; i--)  
          if (isBeginZero)  
             c\[j++\]=result\+'0';  
         else if (result!=0)  
        \{  
            c\[j++\]=result\+'0';  
            isBeginZero = true;  
         \}  
       if (!isBeginZero) c\[j++\]='0';  
       c\[j\]='\\0';  
\}  
int main()  
\{  
      char a\[MAX\_LEN\],c\[MAX\_LEN+10\];  
       int b;  
      scanf("%s",a);  
       scanf("%d",&b);  
       bigNumMul(a,b,c);  
       printf("%s\\n",c);  
       return 0;  
\}*

[format_png]: /images/20230312/617d78e818714b88b771b5a724aaa2c5.png
[format_png 1]: /images/20230312/0889197c752642f0b08458525de339ad.png