#include <stdio.h>
#include <math.h>
#include <time.h>

unsigned long long multiple_karatsuba(unsigned long long x, unsigned long long y);
int number_of_bits (unsigned long long x);

int main()
{
    srand(time(NULL));
    int size = 100;
    printf("Karatsuba\n");

    clock_t begin_time = clock();

    for(int i = 0; i < size; i++) {
        unsigned long long x = rand() % 20000000 + 1000000;
        unsigned long long y = rand() % 20000000 + 1000000;

        //printf("%lu * %lu = %lu\n", x, y, multiple_karatsuba(x, y));
        printf("%lu * %lu = %lu\n", x, y, x * y);
    }

    clock_t end_time = clock();

    printf("Execution time with %d multiplications: %f", size, (end_time - begin_time)/CLOCKS_PER_SEC);

    return 0;
}

unsigned long long multiple_karatsuba(unsigned long long x, unsigned long long y) {
    if (x < 10 && y < 10)
        return x * y;

    int n = 0;

    if(number_of_bits(x) > number_of_bits(y)) {
        n = number_of_bits(x);
    } else {
        n = number_of_bits(y);
    }

    int m = n / 2 + n % 2;

    long a = x / (long) pow(10, m);
    long b = x % (long) pow(10, m);
    long c = y / (long) pow(10, m);
    long d = y % (long) pow(10, m);

    long step1 = multiple_karatsuba(a, c);
    long step2 = multiple_karatsuba(b, d);
    long step3 = multiple_karatsuba(a + b, c + d);
    long step4 = step3 - step2 - step1;

    long step5 = step1 * (long) pow(10, m * 2) + step2 + step4 * (long) pow(10, m);

    return step5;
}

int number_of_bits (unsigned long long x) {
    int counter = 0;
    while(x) {
        counter++;
        x /= 10;
    }
    return counter;
}