I am trying to understand FFT algorithm explained here

FFT(x) {   n=length(x);   
if (n==1) return x;   
m = n/2;   
X = (x_{2j})_{j=0}^{m-1};   
Y = (x_{2j+1})_{j=0}^{m-1};  
X = FFT(X);   
Y = FFT(Y);  
U = (X_{k mod m})_{k=0}^{n-1};   
V = (g^{-k}Y_{k mod m})_{k=0}^{n-1};   
return U+V; 

The author says that the above comes from Danielson-Lanczos Lemma.

I am unable to understand what is the meaning of the lines:

X = (x_{2j})_{j=0}^{m-1};

Y = (x_{2j+1})_{j=0}^{m-1};


The meaning of the first line is "Let $X$ be an array of length $m$ (with indices running from $0$ to $m-1$) such that $X_j = x_{2j}$ for $j \in \{0,\ldots,m-1\}$." The second line has a similar meaning, with $Y_j = x_{2j+1}$ instead.

  • $\begingroup$ Thanks. Which langauge is this BTW? $\endgroup$ – gpuguy Apr 19 '13 at 5:16
  • $\begingroup$ It's pseudocode, so no particular language. $\endgroup$ – Yuval Filmus Apr 19 '13 at 14:36
  • $\begingroup$ @gpuguy: perhaps you meant "which language expresses subscript with _ and superscript with ^ and grouping with { }? The answer is TeX/LaTeX, and various informal kinds of ascii math. Put your statements inside $ signs on Stackexchange and it will magically turn into well formatted math! For example $X = (x_{2j})_{j=0}^{m-1}$ yields $X = (x_{2j})_{j=0}^{m-1}$. $\endgroup$ – Wandering Logic Apr 20 '13 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.