大整数 乘法

代码转自: http://blog.csdn.net/OneGun/archive/2006/05/24/752177.aspx

就是高精度乘
模拟小学时学乘法竖式的方法

比如123*456

首先用一个数组a保存123
a[0]=1; a[1]=2; a[2]=3;
再用另外一个数组b保存456
b[0]=4; b[1]=5; b[2]=6;

做三次高精乘单精，如下：
a乘以b[0]，得到c0数组为
c0[0]=a[0]*b[0]=4
c0[1]=a[1]*b[0]=8
c0[2]=a[2]*b[0]=12
a乘以b[1]，得到c1数组为
c1[0]=a[0]*b[1]=5
c1[1]=a[1]*b[1]=10
c1[2]=a[2]*b[1]=15
同理，a乘以b[2]，得到c2数组为
c2[0]=6
c2[1]=12
c2[2]=18

下一步，是c0 c1 c2三个数组，依次移位相加，得到数组d，如下：
c0[0] c0[1] c0[2]
______c1[0] c1[1] c1[2]
____________c2[0] c2[1] c2[2]
--------------------------------
_d[0]  d[1]  d[2]  d[3]  d[4]
_4     13    28    27    18

最后一步，是对d数组的整理啦
从个位开始，每一位，如果大于9，则求模，前一位进位
for (i=4; i>0; i--)
__if (d[i]>9)
__{
____d[i-1]+=d[i]/10;
____d[i]=d[i]%10;
__}
经过整理，数组d各元素如下：
d[0]  d[1]  d[2]  d[3]  d[4]
5     6     0     8     8

因此，依次输出，得到56088
123*456=56088

大数相乘亦此道理也~





#include <stdio.h>
#include <string.h>
#include <conio.h>

#define Max 100      //这个数可以根据需要调整!

char res[Max];

void Init_char(char *res)
{
int i;
for(i=0; i<Max; i++)
{
  res[i] = '0';
}
return ;
}
void Init_int(int *a)
{
int i;
for(i=0; i< Max; i++)
  a[i] = 0 ;
}

/***********************************************************
* Function    : 大整数相乘
* description : 两个大整数相乘,因为数组的存放方式和我们的乘法
              是互逆的,所以需要从数组的最后一位往前面乘,并把每次
     乘得到的结果先存放在一个数组中,乘完之后直接从这个
     数组读取数据.
* input       :  res 既是一个乘数,也是用于存放相乘结果,为了可以让不同位数的
                    的大整数相乘,把res数组设很大,并在前面添加'0'.
                  mulNum 只是一个乘数而已
* output      :  在相乘之后,把乘积输出.
* backworth   :  No backWorth!
**********************************************************/
void Long_Multy(char *res,char *mulNum)
{
int temp[Max];                  // 用来存放中间结果,用整型数据结构,方便运算!!!
int i,j;
int len;

Init_int(temp);               // 将数组元素都初始化为 0
len = strlen(mulNum);
int t = 0 ;
for(i=len-1; i>=0; i--,t++)   // mulNum 对应的元素
{
  for(j=Max-1; j>=0; j--)   // res 对应的元素
  {
   temp[j-t] += (res[j]-'0') * (mulNum[i]-'0');    // 乘的过程存储!
  }
}

int carry = 0 ;               // 整型结果转化为字符型结果.
for(i=Max-1; i>=0; i--)
{
  res[i] = (temp[i]+carry)%10+'0';
  carry = (temp[i]+carry)/10;
}

//--------------------输出乘积!
printf("相乘的结果为:\n");
for(i=0;i<Max;i++)
  if(res[i] != '0')
   break;
for(i;i<Max;i++)
  putchar(res[i]);
printf("\n");

return ;
}
void input(char *a,char *b)    // 输入需要一些转换,所以单独写成一个函数!
{
int len,i;
scanf("%s %s",a,b);
Init_char(res);
len=strlen(a);
for(i=len-1;i>=0;i--)      //往res数组存放乘数a.
  res[Max+i-len] = a[i];
}


int main()
{
char a[50],b[50];

input(a,b);
Long_Multy(res,b);

getch();
return 0 ;
}