#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int *grade(int *num1, int *num2, int nu);
int *add(int *num1,int nu1,int *num2,int nu2);
int *subtract(int *num1,int nu1,int *num2,int nu2);
int *multiply(int *numb1, int *numb2, int nu);
int *random_num(int n);
int *allocate(int *ans,int start,int *p, int size);
void print_num(int *ans, int nu);
void initialize(int *ans, int nu);
int *grade(int *num1, int *num2, int nu)
{
	int i,j;
	int *ans=(int *)malloc(2*nu*sizeof(int));	
	initialize(ans,nu);
	for(i=0;i<nu;i++)
	{
		for(j=0;j<nu;j++)
		{
			ans[i+j]+=(num1[i]*num2[j]);
			ans[i+j+1]+=(ans[i+j]/2);
			ans[i+j]%=2;
		}
	}
	return ans;
}
			
void initialize(int *ans, int nu)
{
	int i;
	for(i=0;i<nu;i++)
	{
		ans[i]=0;
	}
}
void print_num(int *ans, int nu)
{
	int i;
//	printf("Printing\n");
	for(i=nu-1;i>=0;i--)
	{
		printf("%d",ans[i]);
	}
	printf("\n");
}
int *allocate(int *ans,int start,int *p, int size)
{
	int i,j;
	for(i=start,j=0;j<size;j++,i++)
	{
		ans[i]+=p[j];
		ans[i+1]+=ans[i]/2;
		ans[i]%=2;
	}
	while(ans[i]>1)
	{
//		printf("Allocate loop\n");
		ans[i+1]+=ans[i]/2;
                ans[i]%=2;
	}
	return ans;
}
int *add(int *num1,int nu1,int *num2,int nu2)
{
	int *ans;
//	printf("Addition\n");
	int i;
	if(nu1>=nu2)
	{
		ans=(int *)malloc((nu1+1)*sizeof(int));
		initialize(ans,nu1+1);
//		printf("If\n");
		for(i=0;i<=nu1;i++)
		{
			ans[i]=0;
		}
		for(i=0;i<nu2;i++)
		{
			ans[i]+=(num1[i]+num2[i]);
			ans[i+1]=ans[i]/2;
			ans[i]%=2;
		}
		while(i<nu1)
		{
			ans[i]+=num1[i];
			ans[i+1]=ans[i]/2;
                        ans[i]%=2;
			i++;
		}
	}
	else
	{
		ans=(int *)malloc((nu2+1)*sizeof(int));
		initialize(ans,nu2+1);
//		printf("Else\n");
                for(i=0;i<=nu2;i++)
                {
                        ans[i]=0;
                }
                for(i=0;i<nu1;i++)
                {
                        ans[i]+=(num1[i]+num2[i]);
                        ans[i+1]=ans[i]/2;
                        ans[i]%=2;
                }
//		printf("%d\n%d\n",nu2,nu1);
                while(i<nu2)
                {
//			printf("I<NU2\n");
                        ans[i]+=num2[i];
                        ans[i+1]=ans[i]/2;
                        ans[i]%=2;
			i++;
                }
	}
//	printf("Addition end\n");
	return ans;
}
int *subtract(int *num1,int nu1,int *num2,int nu2)
{
	int i;
	for(i=0;i<nu2;i++)
	{
		if(num1[i]>=num2[i])
		{
			num1[i]-=num2[i];
		}
		else
		{
			num1[i]-=num2[i];
			num1[i]+=2;
			num1[i+1]-=1;
		}
	}
	while(num1[i]<0)
	{
		num1[i]+=2;
		num1[i+1]--;
//		printf("Subtract loop\n");
		i++;
	}
	return num1;
}
	
int *random_num(int n)
{
	int *num=(int *)malloc(n*sizeof(int));
	int i;
//	printf("I am in random_num\n");
	for(i=0;i<n;i++)
	{
		num[i]=rand()%2;
	}
	return num;
}

int *multiply(int *numb1, int *numb2, int nu)
{
	int *answer=(int *)malloc(2*nu*sizeof(int));
//	printf("%d\tMultiply1\n",nu);
	initialize(answer,2*nu);
	int i,j,k;
	/*if(nu==1)
	{
		if((numb1[0]==0)||(numb2[0]==0))
		{
			return answer;
		}
		else
		{
			
			answer[0]=1;
			return answer;
		}
	}
	else if((nu<=3)&&(nu>1))
	{
//		printf("Before multiplication");
//		print_num(answer,(2*nu));
		for(i=0;i<nu;i++)
		{
			for(j=0;j<nu;j++)
			{
				if((numb1[i]==1)&&(numb2[j]==1))
				{
					answer[i+j]+=1;
//					printf("%d\t%d\t\t\t%d\n",i,j,answer[i+j]);
				}
			}
		}
//		printf("Nu is %d\n",nu);
		for(i=0;i<(2*nu);i++)
		{
			if(answer[i]>1)
			{
				answer[i+1]+=(answer[i]/2);
				answer[i]%=2;
			}
		}
//		print_num(answer,(2*nu));
//		printf("Multiply 2 or 3 loop\n");
		return answer;
	}*/
	if(nu<80)
	{
		grade(numb1,numb2,nu);
	}	
	else
	{
		int *bin1, *bin2, *bin3, *bin4, *bin5;
//		printf("%d\tMultiply2\n",nu);
		bin1=answer;
/*		printf("Nu is %d\n",nu);
		printf("Multiply>3 loop\n");
		printf("Bin1 %d\n",bin1[0]);
*/		bin1=multiply(numb1,numb2,nu/2);
/*		printf("Bin1 is");
		print_num(bin1,(2*(nu/2)));
		printf("Before bin2\n");
		bin2=answer+(2*(nu/2));
		printf("%d\n",bin2[0]);
		printf("Nu is %d\n",nu);
*/		bin2=multiply(numb1+(nu/2),numb2+(nu/2),nu-(nu/2));
/*		printf("Bin2 is ");
		
		print_num(bin2,(2*(nu-(nu/2))));
		printf("Nu is %d\n",nu);
*/		
              

        
/*		initialize(bin5,2*((nu+3)/2));
		
		initialize(bin4,((nu+3)/2));
		
		initialize(bin3,((nu+3)/2));	

		printf("Before bin3\n");	
*/                bin3=add(numb1,nu/2,numb1+nu/2,(nu-(nu/2)));
/*        	printf("Nu is %d\n",nu);
		printf("Before bin4"); 
  */              bin4=add(numb2,nu/2,numb2+nu/2,(nu-(nu/2)));		
/*		printf("Nu is %d\n",nu);
		printf("Bin3 is  ");
		
		print_num(bin3,((nu+3)/2));
		
		printf("Bin4 is  ");

              print_num(bin4,((nu+3)/2));
		
*/		
		bin5=multiply(bin3,bin4,(nu+3)/2);
/*		printf("Nu is %d\n",nu);
		printf("Bin5 is  ");

              print_num(bin5,2*((nu+3)/2));
		
		printf("Multiply bin\n");
		
		printf("%d\n",bin3[0]);
*/		
//		free(bin3);

//                free(bin4);
        
                bin5=subtract(bin5,2*((nu+3)/2),bin1,2*(nu/2));
			
/*		printf("Bin5 is  ");

                print_num(bin5,2*((nu+3)/2));
        	printf("Nu is %d\n",nu);
*/                bin5=subtract(bin5,2*((nu+3)/2),bin2,2*(nu-(nu/2)));
		
/*		printf("Bin5 is  ");

                print_num(bin5,2*((nu+3)/2));
	
		printf("%d\n",nu);
		print_num(answer,2*nu);
		printf("Nu is %d\n",nu);
	*/	answer=allocate(answer,nu/2,bin5,2*((nu+3)/2));
		answer=allocate(answer,0,bin1,2*(nu/2));
		answer=allocate(answer,(2*(nu/2)),bin2,(2*(nu-(nu/2))));
		
//		free(bin5);
		
		return answer;
	}
	return answer;
}
int main()
{
	srand ( time(NULL) );
	int n,choice,i,j,k,x;
	int *num1, *num2, *ans;
	int *kr1[100],*kr2[100];
	printf("Enter n, the number of bits in the two numbers\n");
	scanf("%d",&n);
	printf("2\n");
	printf("Enter the choice 1 or 2,1 for seeing the numbers and their products, 2 for the time taken\n");
	scanf("%d",&choice);
	for(x=0;x<100;x++)
	{
		kr1[x]=random_num(n);
		kr2[x]=random_num(n);
	}
	clock_t start=clock();
	num1=random_num(n);
	num2=random_num(n);
	printf("Main\n");
/*	for(i=0;i<2*n;i++)
	{
		ans[i]=0;
	}
*/	ans=multiply(num1,num2,n);
	if(choice==1)
	{
		printf("Num1 is ");
		print_num(num1,n);
		printf("Num2 is ");
        	print_num(num2,n);
		ans=multiply(num1,num2,n);
		printf("Ans by karatsuba is ");
		print_num(ans,2*n);
		ans=grade(num1,num2,n);
		printf("Ans by grade school is ");
                print_num(ans,2*n);
	}
	else
	{
			clock_t start1=clock();
		for(x=0;x<100;x++)
		{
			num1=kr1[x];
			num2=kr2[x];
		//	clock_t start1=clock();
			ans=multiply(num1,num2,n);
		//	clock_t stop=clock();
		}
			clock_t stop=clock();
		printf("Time taken for Karatsuba is %lf microsecond\n",(double)((stop-start1)/100));
			clock_t start2=clock();
		for(x=0;x<100;x++)
		{
			num1=kr1[x];
			num2=kr2[x];	
				ans=grade(num1,num2,n);
				
			
		}
		clock_t stop2=clock();
		printf("Time taken for grade school is %lf microsecond\n",(double)(((stop2-start2))/100));
/*		else
		{
				ans=grade(num1,num2,n);
				clock_t stop2=clock();
				printf("Time taken for grade school is %lf microsecond\n",(double)((stop-start1)));
		}
*/		
	}
	return 0;
}