#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#define N 4
int polynome1[N];
int polynome2[N];
time_t t;

void randomInit(int* array){
	int i = 0;
	for(i = 0; i < N ; i++){
		array[i] = rand() % 12;
	}
}



int * calcul(int * p0, int * p1, int * p2, int n){

    int *calculResult = calloc(2*n-1, sizeof (int));
    int i;

    for (i = 0 ; i < n-1; i++){
        calculResult[i] += p0[i];
        calculResult[i+n/2] += p1[i];
        calculResult[i+n] += p2[i];
    }

    return calculResult;
}

int *add(int *a,int *b,int n){
	int i = 0;
	int *c = calloc(n,sizeof(c));
	for(i = 0; i < n ; i++){
		c[i] = a[i]+b[i];
	}
	return c;
}

int * sub(int * p0, int * p1, int * p2, int n){
    int * subResult = calloc(n, sizeof (int));
    for (int i = 0 ; i < n; i++){
        subResult[i] = p1[i] - p0[i] -p2[i];
    }
    return subResult;
}

int *multiply(int *a,int *b,int n){
	int i,j = 0;
	int *c = calloc(n,sizeof(c));
	for(i = 0; i < n ; i++){
		for(j = 0; j < n ; j++){
			c[j] += a[i] * b[j];
		}
	}
	return c;
}

int* karastuba(int* polynome1,int* polynome2,int n){



	//memcpy(a0,polynome1,n/2);

	//memcpy(b0,polynome2,n/2);
	if(n == 1){
		//return multiply(polynome1,polynome2,n/2);
		        int * res = calloc((n/2), sizeof (int));
        res[0] = polynome1[0] * polynome2[0];
        // pareil que *res = A[0] * B[0]
        return res;
	}
	int *a1 = malloc(sizeof(polynome1)*(n/2));
	int *b1 = malloc(sizeof(polynome2)*(n/2));
	int *a0 = malloc(sizeof(polynome1)*(n/2));
	int *b0 = malloc(sizeof(polynome2)*(n/2));
	/*a0 = polynome1;
	b0 = polynome2;
	a1 = polynome1+n+2;
	b1 = polynome2+n+2;*/

	        int i ;
        for (i = 0 ; i < n/2 ; i++){
            a0[i] = polynome1[i];
            a1[(n/2) -i -1] = polynome1[n-i-1];

            b0[i] = polynome2[i];
            b1[(n/2) -i -1] = polynome2[n-i-1];
        }
	//memcpy(a1,polynome1+(n/2),n/2);
	//memcpy(b1,polynome2+(n/2),n/2);
	int *p2 = karastuba(a1,b1,n/2);
	int *p0 = karastuba(a0,b0,n/2);
	int *p1 = karastuba(add(a1,a0,n/2),add(b1,b0,n/2),n/2);
	p1 = sub(p0,p1,p2,n);


	free(a1);
	free(b1);
	free(a0);
	free(b0);

	return calcul(p0,p1,p2,n);
}

void printPolynome(int *poly,int n){
	int i = 0;
	printf("polynome : [" );
	for(int i = 0; i < n ;i++){
		if(i < n-1)
			printf("%d,",poly[i] );
		else
			printf("%d]",poly[i] );
	}
	printf("\n");

}

int *intToPoly(int a){
	int base = 110;
	int n = 0;
	while(a/base > 0){
		a /= 10;
		n = a;
		printf("%d ",n);
	}
		printf("\n");

}

int main(){
	srand((unsigned) time(&t));
	intToPoly(10);
	randomInit(polynome1);
	randomInit(polynome2);
	printPolynome(polynome1,N);
	printPolynome(polynome2,N);
	int *res = karastuba(polynome1,polynome2,N);
	printPolynome(res,2*N-1);



	return 0;
}