# Optimal Power of N for FFTW

**URL:** <https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232>\
**Category:** Signal and Image Processing\
**Tags:** fftw\
**Created:** [August 3, 2022, 2:03pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232 "2022-08-03T14:03:32Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jake](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jake/32/46007_2.png) [@Jake](https://discourse.julialang.org/u/Jake)\
**Post date:** [August 3, 2022, 2:03pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/1 "2022-08-03T14:03:32Z")

</div>

FFTW is fastest when it has small prime factors according to its manual. If there is the option to pad the input data, then with radix 2 FFT algorithms this is done with a “next power of 2” type function. However if the length is just over a power of 2, at large sizes this can lead to arrays of almost double the length.

I was wondering if anyone has experimented with a “next power of small prime” type of function? In this we would select a range of acceptable primes and then figure out the optimum based on some factor of memory and FFT time.

I have created an example of such a function where it selects the least amount of padding. Comments, suggestions and improvements are welcome.

```julia
using Primes

function nextn(n; maxprime = max(2, ceil(Int, n/10)))
    nextn = typemax(Int) # initialize variable 
    for i in primes(maxprime)
        tmp = nextpow(i, n)
        if tmp < nextn
            nextn = tmp
        end
    end
    return nextn
end

```

---

<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:** [August 3, 2022, 3:13pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/3 "2022-08-03T15:13:02Z")

</div>

Related: [https://rosettacode.org/wiki/N-smooth\_numbers#Julia](https://rosettacode.org/wiki/N-smooth_numbers#Julia)

It might make sense to add a `nextsmooth` function to Primes.jl, analogous to `nextprime`, which returns the next [n-smooth number](https://en.wikipedia.org/wiki/Smooth_number) for a given `n`.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 3, 2022, 3:31pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/4 "2022-08-03T15:31:09Z")

</div>

Sounds like a good idea. Anyone want to make the PR? That said, it might be easier after I push more of the improvements to prime sieving that I’ve started.

---

<div class="post-metadata">

**Author:** ![stillyslalom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stillyslalom/32/45687_2.png) [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)\
**Post date:** [August 3, 2022, 3:56pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/5 "2022-08-03T15:56:40Z")

</div>

Is there any reason not to just use `nextprod` from base Julia?

```julia
julia> nextprod((2, 3, 5, 7), 257)
270

```

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [August 3, 2022, 3:57pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/6 "2022-08-03T15:57:51Z")

</div>

I’ve found 5-smooth numbers give a nice, small-increment set of N’s for FFTW.

---

<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:** [August 3, 2022, 4:02pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/7 "2022-08-03T16:02:27Z")

</div>

> [@stillyslalom](#):
>
> Is there any reason not to just use `nextprod` from base Julia?

Right, I forgot that this function was still in Base (it was [added in 2012](https://github.com/JuliaLang/julia/pull/981) by @tim.holy when `fft` was still in Base. I think it was originally slated to be [moved out of Base](https://github.com/JuliaLang/julia/blob/3653d3d05ffb8a652b12ff22e550ec8fe07edd1d/base/combinatorics.jl#L309), but I guess it was overlooked in Julia 1.0?)

It might still be nice to have a higher-level `nextsmooth(n, x)` function in Primes.jl, which is where I would have expected to find this functionality, though maybe it can call `nextprod` under the hood (unless there is a better algorithm for large `n`?). (For small `n` it can just call `nextprod` with a lookup table of the corresponding primes.)

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [August 3, 2022, 4:06pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/8 "2022-08-03T16:06:46Z")

</div>

Linking related [thread](https://discourse.julialang.org/t/how-to-set-the-length-of-fft/38885/20).

---

<div class="post-metadata">

**Author:** ![stillyslalom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stillyslalom/32/45687_2.png) [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)\
**Post date:** [August 3, 2022, 4:15pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/9 "2022-08-03T16:15:22Z")

</div>

Could this instead be exported by FFTW.jl or AbstractFFTs.jl as a utility function with a sensible set of small primes as a default argument?

---

<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:** [August 3, 2022, 4:19pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/10 "2022-08-03T16:19:52Z")

</div>

An `FFTW.nextfftlen(n)` function would be reasonable, along with `FFTW.nextrfftlen(n)` for real-input FFTs (which favor even lengths). But I think this would be in addition to an N-smooth `nextsmooth` function in Primes.jl.

---

<div class="post-metadata">

**Author:** ![ericphanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ericphanson/32/215186_2.png) [@ericphanson](https://discourse.julialang.org/u/ericphanson)\
**Post date:** [August 3, 2022, 5:47pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/11 "2022-08-03T17:47:41Z")

</div>

DSP.jl has [`nextfastfft`](https://github.com/JuliaDSP/DSP.jl/blob/19c358cc71dbd5f663b6e646b926cbe787f8f165/src/util.jl#L109-L119):

```julia
    nextfastfft(n)
Return the closest product of 2, 3, 5, and 7 greater than or equal
to `n`. FFTW contains optimized kernels for these sizes and
computes Fourier transforms of input that is a product of these
sizes faster than for input of other sizes.

```

---

<div class="post-metadata">

**Author:** ![Jake](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jake/32/46007_2.png) [@Jake](https://discourse.julialang.org/u/Jake)\
**Post date:** [August 3, 2022, 6:05pm UTC](https://discourse.julialang.org/t/optimal-power-of-n-for-fftw/85232/12 "2022-08-03T18:05:18Z")

</div>

> [@Oscar\_Smith](#):
>
> Sounds like a good idea. Anyone want to make the PR? That said, it might be easier after I push more of the improvements to prime sieving that I’ve started.

Thanks all for the great information. As I have never made a pull request, I put in a request for nextsmooth function in the issues section of Primes.jl.