//referenced from:
//http://www.intersrv.com/~dcross/fft.html

#include <iostream>
#include <fstream>
#include <cmath>
#include "fourier.h"
using namespace std;


void Output(long real[], long imag[], int size)
{
	for(int i=0;i<size;i++)
		cout<<real[i]<<'+'<<imag[i]<<" i"<<endl;
}

int main(void)
{ 
	
	int num1,num2,power2;
	long input1[1000],input2[1000];
	long Iminput1[1000],Iminput2[1000];
	long output1[1000],Imoutput1[1000],output2[1000],Imoutput2[1000];
	long result[1000],result1[1000];


	fstream ifile;
	for(int i=0;i<1000;i++)
		 Iminput1[i]=Iminput2[i]=input1[i]=input2[i]=0;

	//read in polynomial one
	ifile.open("input.txt");
	ifile>>num1;
	for(i=0;i<num1;i++)
		ifile>>input1[i];
	

	//read in polynomial two
	ifile>>num2;
	for(i=0;i<num2;i++)
		ifile>>input2[i];

	ifile.close();

	//find out the next 2th power
	power2=(num1>num2)?findthepower(2*num1):findthepower(2*num2);;

	//FFT
	FFT (power2,0,input1,Iminput1,output1,Imoutput1 );
	FFT (power2,0,input2,Iminput2,output2,Imoutput2 );

	//multiply two complex vectors
	multiply(output1, Imoutput1, output2, Imoutput2,input1,Iminput1, power2);

	//do the inversetransform
	FFT(power2, 1, input1,Iminput1,result, result1);

	//output the result
	cout<<endl;
	for(i=0;i<power2;i++)
	{
		cout<<result[i];	cout<<' ';
	} 
	cout<<endl;



	
	
	
	
	//output the normal multiplication

	Multiply(input1,input2,result3);

	//output the result
	cout<<endl;
	for(i=0;i<num1+num2;i++)
	{
		cout<<result3[i];	cout<<' ';
	} 
	cout<<endl;




	return 0;
}