FFT并行MPI实现

FFT算法的MPI实现源代码，编程风格还行，易于理解

#include 
#include 
#include 
#include “mpi.h“

#define MAX_N 50
#define PI    3.1415926535897932
#define EPS   10E-8
#define V_TAG 99
#define P_TAG 100
#define Q_TAG 101
#define R_TAG 102
#define S_TAG 103
#define S_TAG2 104

typedef enum {FALSE TRUE}
BOOL;

typedef struct
{
    double r;
    double i;
} complex_t;

complex_t p[MAX_N] q[MAX_N] s[2*MAX_N] r[2*MAX_N];
complex_t w[2*MAX_N];
int variableNum;
double transTime = 0 totalTime = 0 beginTime;
MPI_Status status;

void comp_add（complex_t* result const complex_t* c1 const complex_t* c2）
{
    result->r = c1->r + c2->r;
    result->i = c1->i + c2->i;
}


void comp_multiply（complex_t* result const complex_t* c1 const complex_t* c2）
{
    result->r = c1->r * c2->r - c1->i * c2->i;
    result->i = c1->r * c2->i + c2->r * c1->i;
}


/*
 * Function:    shuffle
 * Description: 移动f中从beginPos到endPos位置的元素，使之按位置奇偶
 *              重新排列。举例说明:假设数组f，beginPos=2 endPos=5
 *              则shuffle函数的运行结果为f[2..5]重新排列，排列后各个
 *              位置对应的原f的元素为: f[2]f[4]f[3]f[5]
 * Parameters:  f为被操作数组首地址
 *              beginPos endPos为操作的下标范围
 */
void shuffle（complex_t* f int beginPos int endPos）
{
    int i;
    complex_t temp[2*MAX_N];

    for（i = beginPos; i <= endPos; i ++）
    {
        temp[i] = f[i];
    }

    int j = beginPos;
    for（i = beginPos; i <= endPos; i +=2）
    {
        f[j] = temp[i];
        j++;
    }
    for（i = beginPos +1; i <= endPos; i += 2）
    {
        f[j] = temp[i];
        j++;
    }
}


/*
 * Function:		evaluate
 * Description:	对复数序列f进行FFT或者IFFT（由x决定），结果序列为y，
 * 			产生leftPos 到 rightPos之间的结果元素
 * Parameters:	f : 原始序列数组首地址
 * 			beginPos : 原始序列在数组f中的第一个下标
 * 			endPos : 原始序列在数组f中的最后一个下标
 * 			x : 存放单位根的数组，其元素为ww^2w^3...
 * 			y : 输出序列
 * 			leftPos : 所负责计算输出的y的片断的起始下标
 * 			rightPos : 所负责计算输出的y的片断的终止下标
 * 			totalLength : y的长度
 */
void evaluate（complex_t* f int beginPos int endPos
const complex_t* x complex_t* y
int leftPos int rightPos int totalLength）
{
    int i;
    if （（beginPos > endPos）||（leftPos > rightPos））
    {
        printf（“Error in use Polynomial!\n“）;
        exit（-1）;
    }
    else if（beginPos == endPos）
    {
        for（i = leftPos; i <= rightPos; i ++）
        {
            y[i] = f[beginPos];
        }
    }
    else if（beginPos + 1 == endPos）
    {
        for（i = leftPos; i <= rightPos; i ++）
        {
            complex_t temp;
            comp_multiply（&temp &f[endPos] &x[i]）;
            comp_add（&y[i] &f[beginPos] &temp）;
        }
    }
    else
    {
        complex_t tempX[2*MAX_N]tempY1[2*MAX_N] tempY2[2*MAX_N];
        int midPos = （beginPos + endPos）/2;

        shuffle（f beginPos endPos）;

        for（i = leftPos; i <= rightPos; i ++）
        {
            comp_multiply（&tempX[i] &x[i] &x[i]）;
        }

        evaluate（f beginPos midPos tempX tempY1
            leftPos rightPos totalLength）;
        evaluate（f midPos+1 endPos tempX tempY2
            leftPos rightPos total

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      57350  2010-01-27 10:19  新建文件夹\data.txt

     文件         24  2003-07-14 02:22  新建文件夹\dataIn.txt

     文件      21553  2010-01-27 10:22  新建文件夹\dataout.txt

     文件      10722  2003-07-14 03:19  新建文件夹\fft.c

     文件        471  2003-07-14 02:22  新建文件夹\readme.txt

     目录          0  2010-04-14 16:51  新建文件夹

----------- ---------  ---------- -----  ----

                90120                    6