FFT(a, n)
    for i = 0..2**k-1
        f[rev[i]] = a[i]
    for t = 0..k-1
        // f[0..2**t)[2**t..2**(t+1)) -- recursive calls
        // f[0..2**(t+1))             -- that's what we want to get
        for (i = 0; i < 2**k; i += 2**(t+1))
            for j = 0..2**t-1
                tmp = f[i+j+2**t] * root[j << (k - t - 1)]
                f[i+j+2**t]=f[i+j]-tmp
                f[i+j]=f[i+j]+tmp