\myheading{Fast Fourier transform}

I've found one of the smallest possible FFT implementations on \href{https://www.reddit.com/r/Python/comments/1la4jp/understanding_the_fft_algorithm_with_python/}{reddit}:

\lstinputlisting[style=custompy]{\CURPATH/3_FFT/FFT.py}

Just interesting, what value has each element on output?

\lstinputlisting[style=custompy]{\CURPATH/3_FFT/FFT_symb.py}

FFT() function left almost intact, the only thing I added: complex value is converted into string and then
Expr() object is constructed.

\lstinputlisting{\CURPATH/3_FFT/res1.txt}

We can see subexpressions in form like $x^0$ and $x^1$.
We can eliminate them, since $x^0=1$ and $x^1=x$.
Also, we can reduce subexpressions like $x \cdot 1$ to just $x$.

\begin{lstlisting}
    def __mul__(self, other):
        op1=self.s
        op2=self.convert_to_Expr_if_int(other).s

        if op1=="1":
            return Expr(op2)
        if op2=="1":
            return Expr(op1)

        return Expr("(" + op1 + "*" + op2 + ")")

    def __pow__(self, other):
        op2=self.convert_to_Expr_if_int(other).s
        if op2=="0":
            return Expr("1")
        if op2=="1":
            return Expr(self.s)

        return Expr("(" + self.s + "**" + op2 + ")")
\end{lstlisting}

\lstinputlisting{\CURPATH/3_FFT/res2.txt}