karatsuba.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#define NDEBUG

int size(int n) {
    int c = 0;
    while (n) {
        n /= 10;
        c++;
    }
    return c;
}

int start(int n, int m) {
    return n / (int)(pow(10, m));
}

int end(int n, int m) {
    return n % (int) pow(10, size(n) - m);
}

int km(int x, int y) {
    if (x < 10 || y < 10) {
        return x * y;
    }
    int size_x = size(x);
    int size_y = size(y);
    int m = size_x > size_y ? size_x / 2 : size_y / 2;

    int x0 = start(x, m);
    int x1 = end(x, m);
    int y0 = start(y, m);
    int y1 = end(y, m);

    int z0 = km(x1, y1);
    int z2 = km(x0, y0);
    int z1 = km((x1 + x0), (y1 + y0)) - z0 - z2;
    
    return z2 * (int) pow(10, (double) (2 * m)) + z1 * (int) pow(10, (double)m) + z0;
}

int main() {
    printf("%d", km(12, 34));
    return 0;
}