Return to Answer

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 an "unscaled" dft, using mir and idft (which is ifft here):

 import numpy.fft as fft def dft(xin) : return fft.ifft(mir(xin)) 

I first mirror the frequencies to implement idft as radix-2 DIT, allowing in turn to 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] W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] #twiddle return (G + W * H) / 2 

UPDATE: OverLordGoldDragon gave a solution that is superior to mine on every aspect. He got rid of mirroring, but more importantly he clearly exposed the insight to solve this problem. I hope he gets a shower of points!

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 an "unscaled" dft, using mir and idft (which is ifft here):

 import numpy.fft as fft def dft(xin) : return fft.ifft(mir(xin)) 

I first mirror the frequencies to implement idft as radix-2 DIT, allowing in turn to 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] W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] #twiddle return (G + W * H) / 2 

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 

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 an "unscaled" dft, using mir and idft (which is ifft here):

  import numpy.fft as fft     def dft(xin) : return fft.ifft(mir(xin)) 

I first mirror the frequencies to implement idft as radix-2 DIT, allowing in turn to 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] W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] #twiddle return (G + W * H) / 2 

It turns out to be not that difficult.

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 

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