---

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.

Functions
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: http://www.cag.lcs.mit.edu/streamit/results/fft/code/c/unifft.c

Definition in file fft.c.

---

Function Documentation

int bitrev (  int    inp, int    numbits )  [static]

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 )  [static]

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 )  [static]

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]

Returns: 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 )  [static]

permutes the array using a bit-reversal permutation Definition at line 129 of file fft.c. References bitrev, and log_2. Referenced by main.

---