# FFT implementation using Danielson-Lanczos Lemma

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.
• @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}\$. – Wandering Logic Apr 20 '13 at 13:00