It turns out to be not that difficult. At least when N is a power of 2.
The cornerstone of my approach is mirroring. Vanilla code (python):
import numpy as np def mir(xin): n = xin.shape[0] return np.array([xin[-i & (n - 1)] for i in range(n)]) Now I can build dft, using mir and idft (which is ifft here):
import numpy.fft as fft def dft(xin) : return fft.ifft(mir(xin) * xin.shape[0]) Now I can rely on radix-2 DIT, and reconstruct only half of the signal. But I need twiddle factors.
def split(xin) : t = np.transpose(xin.reshape(-1, 2)) return t[0], t[1] def ifft_half(c): e, o = split(mir(c)) G = dft(e) H = dft(o) N = c.shape[0] #twiddle factors W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] return (G + W * H) / N