#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[]) 
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.

treats inp as a numbits number and bitreverses it. inp < 2^(numbits) for meaningful bitreversal Definition at line 156 of file fft.c. Referenced by compute_W, and permute_bitrev. 

W will contain roots of unity so that W[bitrev(i,log2n1)] = e^(2*pi*i/n) n should be a power of 2 Note: W is bitreversal permuted because fft(..) goes faster if this is done. see that function for more details on why we treat 'i' as a (log2n1) bit number. Definition at line 113 of file fft.c. Referenced by main. 

fft on a set of n points given by A_re and A_im. Bitreversal permuted rootsofunity 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. 

Definition at line 170 of file fft.c. Referenced by compute_W, and permute_bitrev. 

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. 

permutes the array using a bitreversal permutation Definition at line 129 of file fft.c. Referenced by main. 