Main Page   Alphabetical List   Data Structures   File List   Data Fields   Globals  

fft.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <malloc.h>
#include <sys/time.h>
#include "tuple.h"

Go to the source code of this file.


void compute_W (int n, double *W_re, double *W_im)
void permute_bitrev (int n, double *A_re, double *A_im)
int bitrev (int inp, int numbits)
int log_2 (int n)
void fft (int n, double *A_re, double *A_im, double *W_re, double *W_im)
int main (int argc, char *argv[])

Detailed Description

This is adapted from some reference FFT C code found at:

Definition in file fft.c.

Function Documentation

int bitrev int    inp,
int    numbits

treats inp as a numbits number and bitreverses it. inp < 2^(numbits) for meaningful bit-reversal

Definition at line 156 of file fft.c.

Referenced by compute_W, and permute_bitrev.

void compute_W int    n,
double *    W_re,
double *    W_im

W will contain roots of unity so that W[bitrev(i,log2n-1)] = e^(2*pi*i/n)

n should be a power of 2

Note: W is bit-reversal permuted because fft(..) goes faster if this is done. see that function for more details on why we treat 'i' as a (log2n-1) bit number.

Definition at line 113 of file fft.c.

References bitrev, and log_2.

Referenced by main.

void fft int    n,
double *    A_re,
double *    A_im,
double *    W_re,
double *    W_im

fft on a set of n points given by A_re and A_im. Bit-reversal permuted roots-of-unity lookup table is given by W_re and W_im. More specifically, W is the array of first n/2 nth roots of unity stored in a permuted bitreversal order. n must be a power of 2 to work.

Execution time on a 450MHz PIII is about n * log2(n) * 1.2 usecs.

Definition at line 188 of file fft.c.

Referenced by main.

int log_2 int    n [static]

log n (to the base 2), if n is positive and power of 2

Definition at line 170 of file fft.c.

Referenced by compute_W, and permute_bitrev.

int main int    argc,
char *    argv[]

Find out where the tuple server is. Go into a loop: get a request to perform an FFT operation, perform it, and put the result back in the tuple space.

Three fields in the request tuple are used as unique identifiers to make sure the customer reclaims the correct result, in case several FFTs are being done simultaneously. These identifier fields can be initialized using random_int() in tuple.c.

Definition at line 35 of file fft.c.

References compute_W, element::data, tuple::elements, fft, get_server_portnumber, get_tuple, make_tuple, permute_bitrev, context::portnumber, put_tuple, context::servername, and tuple_string_field.

void permute_bitrev int    n,
double *    A_re,
double *    A_im

permutes the array using a bit-reversal permutation

Definition at line 129 of file fft.c.

References bitrev, and log_2.

Referenced by main.

Generated on Sun Mar 30 23:46:50 2003 by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002