There is a well-known algorithm which uses padding to the nearest power of two, so dft could be found by standart D&C technique. I have a problem which requires solving linear equation with circulant matrix. There is a formula, which I need to use at a certain step
$$$x=IFFT(\frac{FFT(c)}{FFT(b)})$$$
And I need here to find FFT of both vectors without padding. I don't really understand how should i do it without really struggling (like D&C and strangely divide vectors then multiply not by -1 but by some power of root of unity and then do some random stuff). There is a built-in function in pandas(actually there is even solve_circulant function in scipy), but i can't use them (because cf doesn't provide numpy :) ). Is there a relatively easy way to calculate it(mb using result with padding) or maybe there is a source(python/C++) which i could just copy for my purposes?
I had the same issue when i was doing the recent Div 3, E. But i did not find a way of solving it.
yeah, i want to solve generalization of this problem(i guess it's quite an overkill for problem itself)