c语言实现1024bit大数乘法(3)c/c++weixin44830789的博客-

记录大数相乘的一般思路，乘法只是正数的大数相乘，数组第0位代表数组长度。
z[1]=x[1]*y[1]
z[2]=x[1]*y[2] +x[2]*y[1]
z[3]=x[1]*y[3] +x[2]*y[2]+x[3]*y[1]
…
因此可得z[i]=x[i-j+1]*y[j], for j=1到 y[0]， x[0]> i-j>=0
考虑到进为问题，得到如下程序

 Init(t);   t[0] = x[0] + y[0] - 1; for (i = 1; i <= t[0]; i++) {    sum = carry;    carry = 0; for (j = 1; j <= y[0]; j++) { if ((i - j) >= 0 && (i - j) < x[0]) {      mul = x[i - j + 1];      mul = (unsigned long long)mul * y[j];      carry = carry + mul / 0x100000000;      mul = mul & 0xffffffff;      sum = sum + mul; } }    carry = carry + sum / 0x100000000;    t[i] = (unsigned int)sum; } 

全部代码如下

/**************************************************************************************************** 大数相乘 调用方式Mul(x,y,z) 返回值，z=x*y *****************************************************************************************************/ void Mul_Long(unsigned int x[], unsigned long long y, unsigned int *z) { unsigned int t[34]; unsigned long long mul; unsigned int carry = 0; int i; Init(t); Mov_Big(x, t); for (i = 1; i <= x[0]; i++) {   mul = x[i];   mul = mul * y + carry;   t[i] = (unsigned int)mul;   carry = (unsigned int)(mul >> 32); } if (carry != 0) {   t[0]++;   t[t[0]] = carry; }  i = t[0]; while (t[i] == 0 && i > 1) //这里有改动i>1  {   t[0]--;   i--; } Mov_Big(t, z); } void Mul_Big(unsigned int x[], unsigned int y[], unsigned int *z) { unsigned int t[100]; unsigned long long sum, mul = 0, carry = 0; unsigned int i, j; if (y[0] == 1) Mul_Long(x, y[1], z); else { Init(t);   t[0] = x[0] + y[0] - 1; for (i = 1; i <= t[0]; i++) {    sum = carry;    carry = 0; for (j = 1; j <= y[0]; j++) { if ((i - j) >= 0 && (i - j) < x[0]) {      mul = x[i - j + 1];      mul = (unsigned long long)mul * y[j];      carry = carry + mul / 0x100000000;      mul = mul & 0xffffffff;      sum = sum + mul; } }    carry = carry + sum / 0x100000000;    t[i] = (unsigned int)sum; } if (carry != 0) {    t[0]++;    t[t[0]] = (unsigned int)carry; }   i = t[0]; while (t[i] == 0 && i > 1)//这里有改动  {    t[0]--;    i--; } Mov_Big(t, z); } }