main.c

使用FFT实现的两个多项式相乘的算法。 输入文件： 第一行为(n-1) 第二行为第一个多项式系数序列 第三行为第二个多项式系数序列 系数序列的格式为：an,an-1,an-2 ,…, a1

#include <stdio.h>
#include <malloc.h>
#include "FFT.h"
#include <math.h>

void main(int argc, char *argv[])
{
	FILE* pFile;
	int MaxExpo, i, Max;
	int* Co;
	poly p1, p2;
	MyComplex C;
	double angle;
	MyComplex *P1, *P2, *P3, *P4, *P1Coefficient, *P2Coefficient;

	if(argc <= 2)
	{
		printf("input example: \n FFT input.dat output.dat \n 5060309181\n");
		return;
	}

	pFile = fopen(argv[1], "r");
	if(pFile == 0)
		return;
	fscanf(pFile, "%d\n", &MaxExpo);

	Max = GetUpExpo(MaxExpo * 2);

	Co = (int*)malloc(sizeof(int) * Max);
	
	for(i = 0; i < MaxExpo + 1; i++)
		fscanf(pFile, "%d", &Co[i]);
	for(; i < Max; i++)
		Co[i] = 0;
	InitializePoly(&p1, Max - 1, Co);
	
	for(i = 0; i < MaxExpo + 1; i++)
		fscanf(pFile, "%d", &Co[i]);
	for(; i < Max; i++)
		Co[i] = 0;
	InitializePoly(&p2, Max - 1, Co);

	P1Coefficient = (MyComplex*)malloc(sizeof(MyComplex) * Max);
	for(i = 0; i < Max; i++)
	{
		P1Coefficient[i].real = p1.Coefficient[i];
		P1Coefficient[i].imagine = 0;
	}
	
	P2Coefficient = (MyComplex*)malloc(sizeof(MyComplex) * Max);
	for(i = 0; i < Max; i++)
	{
		P2Coefficient[i].real = p2.Coefficient[i];
		P2Coefficient[i].imagine = 0;
	}

	angle = 360 / (double)Max;
	angle = angle * PI / 180;
	C.imagine = sin(angle);
	C.real = cos(angle); 
	P1 = FFT(Max, P1Coefficient, C);
	P2 = FFT(Max, P2Coefficient, C);
	P3 = (MyComplex*)malloc(sizeof(MyComplex) * Max);
	for(i = 0; i < Max; i++)
		Equal(&P3[i], Mult(P1[i], P2[i]));

	P4 = FFT(Max, P3, Inv(C));
	
	pFile = fopen(argv[2], "w");
	for(i = 0; i < MaxExpo * 2 + 1; i++)
		fprintf(pFile, "%.0f ", P4[i].real / Max);
}