# How to set the length of fft

**URL:** <https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885>\
**Category:** General Usage\
**Tags:** fftw\
**Created:** [May 6, 2020, 1:23pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885 "2020-05-06T13:23:55Z")\
**Posts on this page:** 7\
**Page:** 2

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 7, 2020, 5:08pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/21 "2020-05-07T17:08:13Z")

</div>

> [@RoyiAvital](#):
>
> I just want to understand what happens when we see a code in MATLAB or Python that does so.

As I said, if you use the padding option in Matlab or Python’s `fft` functions, it is just zero padding and computing the same thing as the “manual” 2-line Julia padding code above.

But this is not something you want to do blindly because it changes the transform you are computing (much more than a trivial change in normalization).

> I am not into the Mathematical definitions.

You have to define mathematically what transform you want. There are infinitely many ways to have DFT-like functions with N inputs and M outputs, such as zero-padding the input (if M \> N) or doing some other sampling in the frequency domain (as in a “Zoom FFT”).

Typically, what people do corresponds to a discrete-time Fourier transform (DTFT) with some window function implied for the input and some sampling in frequency domain for the output, but the choices of windowing and frequency-sampling matter a lot (and determine what algorithms are applicable)!

You may not be “into” it, but not understanding what you are doing is a good way to get incorrect results.

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [May 7, 2020, 5:08pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/22 "2020-05-07T17:08:55Z")

</div>

Alright, thanks!

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [May 7, 2020, 5:33pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/23 "2020-05-07T17:33:44Z")

</div>

> [@stevengj](#):
>
> > [@RoyiAvital](#):
> >
> > I just want to understand what happens when we see a code in MATLAB or Python that does so.
> 
> As I said, if you use the padding option in Matlab or Python’s `fft` functions, it is just zero padding and computing the same thing as the “manual” 2-line Julia padding code above.
> 
> But this is not something you want to do blindly because it changes the transform you are computing (much more than a trivial change in normalization).
> 
> > I am not into the Mathematical definitions.
> 
> You have to define mathematically what transform you want. There are infinitely many ways to have DFT-like functions with N inputs and M outputs, such as zero-padding the input (if M \> N) or doing some other sampling in the frequency domain (as in a “Zoom FFT”).
> 
> Typically, what people do corresponds to a discrete-time Fourier transform (DTFT) with some window function implied for the input and some sampling in frequency domain for the output, but the choices of windowing and frequency-sampling matter a lot (and determine what algorithms are applicable)!
> 
> You may not be “into” it, but not understanding what you are doing is a good way to get incorrect results.

I do understand it deeply. This is what I do.  
I meant in the context of this thread I thought it is obvious that we’re talking about what’s people usually mean.  
If you want it more rigorously, I’d define it by the [DFT Matrix](https://en.wikipedia.org/wiki/DFT_matrix) as this is what usually people mean when they says the case of N \to M .  
I was under the impression FFT Libraries have optimized code path for those cases as well.  
Since not every day we have a chance to ask an expert like you in the field I was wondering if there is something I miss in FFTW’s documentation about this.  
Specifically I was almost sure that the “easy” case (Where M \> N ) has a special treatment,

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 7, 2020, 5:42pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/24 "2020-05-07T17:42:42Z")

</div>

> [@RoyiAvital](#):
>
> If you want it more rigorously, I’d define it by the [DFT Matrix](https://en.wikipedia.org/wiki/DFT_matrix) as this is what usually people mean when they says the case of N→M N \to M .

The DFT matrix is square (as in the Wikipedia article you linked). A non-square transform is not a DFT in any sense (regardless of normalization). I guess you mean a zero-padded DFT (i.e. the first N columns of an MxM DFT), but if that is what you want you need to say so. There are infinitely many possible non-square Fourier-like transforms and they can all be represented as matrices. e.g. a chirp-z transform is also a very common and useful choice.

> [@RoyiAvital](#):
>
> I was under the impression FFT Libraries have optimized code path for those cases as well.

Nope, not typically.

See my [comments/links above](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/5). A pruned FFT is theoretically possible, but only becomes practically beneficial (for 1d transforms) when you zero pad by a lot (multiplying the length by a large factor, typically 100x or more), and if you are doing this probably a “Zoom FFT” is better for you anyway (but is a different beast because you have to specify the desired frequency sampling).

For example, you can see [numpy’s zero-padding code](https://github.com/numpy/numpy/blob/8931a70dbe29e0964cffbbf7637464229688c833/numpy/fft/_pocketfft.py#L69-L71), which is precisely the trivial algorithm I suggested [above](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/2).

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [May 7, 2020, 6:09pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/25 "2020-05-07T18:09:12Z")

</div>

> [@stevengj](#):
>
> > [@RoyiAvital](#):
> >
> > If you want it more rigorously, I’d define it by the [DFT Matrix](https://en.wikipedia.org/wiki/DFT_matrix) as this is what usually people mean when they says the case of N→M N \to M .
> 
> The DFT matrix is square (as in the Wikipedia article you linked). A non-square transform is not a DFT in any sense (regardless of normalization). I guess you mean a zero-padded DFT (i.e. the first N columns of an MxM DFT), but if that is what you want you need to say so. There are infinitely many possible non-square Fourier-like transforms and they can all be represented as matrices. e.g. a chirp-z transform is also a very common and useful choice.

OK, In order to be exact I meant the matrix form of:

X \left[k \right] = \sum\_{n = 0}^{N - 1} x \left[n \right] {e}^{-j 2 \pi \frac{k n}{M} }, \; k \in \left\{ 0, 1, 2, \ldots, M - 1 \right\}

OK, I was under the impression (With little knowledge about how it’s implemented) that it would be easy to tell the FFT algorithm how to “extrapolate” M - N zeros without actually having them in the array.

Thank you for sharing that knowledge.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 7, 2020, 6:10pm UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/26 "2020-05-07T18:10:25Z")

</div>

> [@antoine-levitt](#):
>
> `nextprod([2, 3, 5], N)`

Wow! Thank you! I didn’t know about that function.

I normally use an algorithm from a function on the Matlab File Exchange: [FFTWN: Round up to efficient FFT integer - File Exchange - MATLAB Central](https://se.mathworks.com/matlabcentral/fileexchange/36705-fftwn-round-up-to-efficient-fft-integer)  
The description on its page has this to say:

> The MATLAB FFT implementation uses the FFTW library. With default  
> settings, FFTW is highly efficient for data lengths of the form  
> N = 2^a_3^b_5^c_7^d_11^e\*13^f, where e + f = 0 or 1, and the rest  
> of the exponents are arbitrary.

So that’s what it does, finds the next N that satisfies that expression. I wonder if that statement is actually accurate!

As for how the zero-padding is actually accomplished (after having found an efficient length), for me it’s less about performance, and more about having a convenient interface. That’s why I enjoy having the padding length as part of the interface.

(BTW: Julia’s `nextprod` is 50 times faster than the Matlab function, naturally 😃 )

---

<div class="post-metadata">

**Author:** ![ssfrr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ssfrr/32/3736_2.png) [@ssfrr](https://discourse.julialang.org/u/ssfrr)\
**Post date:** [May 8, 2020, 1:03am UTC](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/27 "2020-05-08T01:03:35Z")

</div>

> [@antoine-levitt](#):
>
> I currently do `nextprod([2, 3, 5], N)`

FWIW this (including `7` as well) is how `DSP.nextfastfft` is implemented ([here](https://github.com/JuliaDSP/DSP.jl/blob/f6c051d562dd7422c52f9628fccf391c6413723b/src/util.jl#L110-L122)). If there’s a better heuristic that would be a good place to make the improvement.

[Previous page](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885.md?page=1)
