用分治法写一个大数相乘的C语言代码

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

void add(char *a, char *b, char *sum) //大数相加函数
{
int i, j, k = 0, carry = 0, lena = strlen(a), lenb = strlen(b);
for (i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--) //从低位到高位依次相加，不足位补0
{
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int s = x + y + carry;
sum[k++] = s % 10 + '0';
carry = s / 10;
}
if (carry) //如果最高位有进位，将进位加到结果中
sum[k++] = carry + '0';
sum[k] = '\0'; //字符串结尾
for (i = 0, j = k - 1; i < j; i++, j--) //将结果翻转
{
char temp = sum[i];
sum[i] = sum[j];
sum[j] = temp;
}
}

void multiply(char *a, char *b, char *result) //大数相乘函数
{
int lena = strlen(a), lenb = strlen(b);
if (lena < lenb) //保证a的位数大于等于b的位数
{
char *temp = a;
a = b;
b = temp;
int temp_len = lena;
lena = lenb;
lenb = temp_len;
}
if (lenb == 0) //如果有一个数为0，结果就为0
{
result[0] = '0';
result[1] = '\0';
return;
}
if (lenb == 1) //如果b只有一位，直接按位乘
{
int i, carry = 0, x = b[0] - '0';
for (i = lena - 1; i >= 0; i--)
{
int s = (a[i] - '0') * x + carry;
result[i + 1] = s % 10 + '0';
carry = s / 10;
}
if (carry) //如果最高位有进位，将进位加到结果中
result[0] = carry + '0';
else
result[0] = '0';
result[lena + (carry ? 1 : 0)] = '\0'; //字符串结尾
return;
}
int i, j;
char *a1 = (char *)malloc((lena / 2 + 1) * sizeof(char)); //将a分为两部分，a1为低位部分
char *a2 = (char *)malloc((lena - lena / 2 + 1) * sizeof(char)); //a2为高位部分
char *b1 = (char *)malloc((lenb / 2 + 1) * sizeof(char)); //将b分为两部分，b1为低位部分
char *b2 = (char *)malloc((lenb - lenb / 2 + 1) * sizeof(char)); //b2为高位部分
char *a1b1 = (char *)malloc((lena / 2 + lenb / 2 + 2) * sizeof(char)); //a1*b1
char *a2b2 = (char *)malloc((lena - lena / 2 + lenb - lenb / 2 + 2) * sizeof(char)); //a2*b2
char *temp1 = (char *)malloc((lena / 2 + lenb / 2 + 2) * sizeof(char)); //a1+a2和b1+b2的和
char *temp2 = (char *)malloc((lena / 2 + lenb / 2 + 2) * sizeof(char)); //(a1+a2)*(b1+b2)的差
for (i = 0; i < lena / 2; i++) //分割a
a1[i] = a[i];
a1[i] = '\0';
for (i = lena / 2; i < lena; i++)
a2[i - lena / 2] = a[i];
a2[i - lena / 2] = '\0';
for (i = 0; i < lenb / 2; i++) //分割b
b1[i] = b[i];
b1[i] = '\0';
for (i = lenb / 2; i < lenb; i++)
b2[i - lenb / 2] = b[i];
b2[i - lenb / 2] = '\0';
multiply(a1, b1, a1b1); //递归计算a1*b1
multiply(a2, b2, a2b2); //递归计算a2*b2
add(a1, a2, temp1); //计算a1+a2
add(b1, b2, temp2); //计算b1+b2
multiply(temp1, temp2, temp2); //递归计算(a1+a2)*(b1+b2)
for (i = 0; i < lena; i++) //将(a1+a2)*(b1+b2)减去a1*b1和a2*b2的和
temp2[i] -= a1b1[i] + a2b2[i] - '0';
for (i = 0; i < lena / 2; i++) //将a1*b1左移两倍的位数
a1b1[lena - i] = a1b1[lena / 2 - i - 1];
for (i = lena / 2; i < lena; i++)
a1b1[i] = '0';
a1b1[lena] = '\0';
add(a1b1, a2b2, result); //将a1*b1和a2*b2的和加上(a1+a2)*(b1+b2)减去a1*b1和a2*b2的和
add(result, temp2, result);
free(a1);
free(a2);
free(b1);
free(b2);
free(a1b1);
free(a2b2);
free(temp1);
free(temp2);
}

int main()
{
char a[1000], b[1000], result[2000];
printf("请输入两个大数：\n");
scanf("%s%s", a, b);
multiply(a, b, result);
printf("%s\n", result);
return 0;
}