C语言程序用Karatsuba乘法实现两个大整数相乘

好的，以下是使用C语言程序实现Karatsuba乘法的示例代码：

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

#define MAX_LEN 1000

void add(char *a, char *b) {
    int lena = strlen(a), lenb = strlen(b);
    int i, j, len = lena > lenb ? lena : lenb;
    for (i = len - 1, j = 0; i >= 0; i--, j++) {
        int numa = i >= lena ? 0 : a[i] - '0';
        int numb = i >= lenb ? 0 : b[i] - '0';
        int sum = numa + numb + j;
        a[i] = sum % 10 + '0';
        j = sum / 10;
    }
}

void karatsuba(char *x, char *y, char *z) {
    int lenx = strlen(x), leny = strlen(y), lenz;
    char *x1, *x0, *y1, *y0, *p1, *p2, *p3, *t1, *t2;
    char *z1, *z2, *z3, *tmp1, *tmp2;
    int n, n2, i;

    if (lenx < leny) {
        char *tmp = x;
        x = y;
        y = tmp;
        lenx ^= leny ^= lenx ^= leny;
    }

    if (lenx < 10 || leny < 10) {
        int val = 0;
        for (i = 0; i < lenx; i++) {
            val = val * 10 + x[i] - '0';
        }
        for (i = 0; i < leny; i++) {
            val = val * 10 + y[i] - '0';
        }
        sprintf(z, "%d", val);
        return;
    }

    n = lenx > leny ? lenx : leny;
    n2 = n / 2;

    x1 = x + n2;
    x0 = x;
    y1 = y + n2;
    y0 = y;

    p1 = (char *)malloc(MAX_LEN);
    p2 = (char *)malloc(MAX_LEN);
    p3 = (char *)malloc(MAX_LEN);
    t1 = (char *)malloc(MAX_LEN);
    t2 = (char *)malloc(MAX_LEN);
    z1 = (char *)malloc(MAX_LEN);
    z2 = (char *)malloc(MAX_LEN);
    z3 = (char *)malloc(MAX_LEN);
    tmp1 = (char *)malloc(MAX_LEN);
    tmp2 = (char *)malloc(MAX_LEN);

    karatsuba(x1, y1, p1);
    karatsuba(x0, y0, p2);
    add(x1, x0);
    add(y1, y0);
    karatsuba(x1, y1, p3);
    sprintf(t1, "%0*d", n + n2, 0);
    sprintf(t2, "%0*d", n2, 0);
    strncpy(t1, p1, strlen(p1));
    strncpy(t2, p3, strlen(p3) - strlen(p1) - strlen(p2));
    add(t1, t2);
    sprintf(z1, "%0*d", n + n2, 0);
    strncpy(z1, t1, strlen(t1));
    strncpy(z2, p2, strlen(p2));
    sprintf(tmp1, "%0*d", n, 0);
    sprintf(tmp2, "%0*d", n2, 0);
    strncpy(tmp1, z1, strlen(z1));
    strncpy(tmp2, z2, strlen(z2));
    add(tmp1, tmp2);
    strncpy(z3, p3 + strlen(p1) + strlen(p2), strlen(p3) - strlen(p1) - strlen(p2));
    sprintf(z, "%0*d", n * 2, 0);
    strncpy(z + n2, tmp1, strlen(tmp1));
    strncpy(z, z1, strlen(z1));
    strncpy(z + 2 * n2, z2, strlen(z2));
    strncpy(z + 3 * n2, z3, strlen(z3));

    free(p1);
    free(p2);
    free(p3);
    free(t1);
    free(t2);
    free(z1);
    free(z2);
    free(z3);
    free(tmp1);
    free(tmp2);
}

int main() {
    char x[MAX_LEN], y[MAX_LEN], z[MAX_LEN * 2];
    scanf("%s%s", x, y);
    karatsuba(x, y, z);
    printf("%s\n", z);
    return 0;
}

该程序使用了递归的思想实现Karatsuba乘法，具体实现过程与前面的Python示例代码类似，不同之处在于需要手动实现字符串相加和字符串补0等操作，以及需要使用动态内存分配来存储中间结果和最终结果。