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 al…

Related: 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 for a given n.

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.

Is there any reason not to just use nextprod from base Julia? julia> nextprod((2, 3, 5, 7), 257) 270

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

[image] 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 by @tim.holy when fft was still in Base. I think it was originally slated to be moved out of Base , but I guess it was overlooked in J…

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?

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.

DSP.jl has nextfastfft : 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.

[image] 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 funct…

Optimal Power of N for FFTW

Specific Domains Signal and Image Processing

rafael.guerra August 3, 2022, 4:06pm 8

Linking related thread.

Topic		Replies	Views
How to set the length of fft General Usage fftw	26	5151	May 8, 2020
[ANN] RustFFT.jl: Compute forward and inverse FFTs with RustFFT Package Announcements	13	1651	May 30, 2023
Computing a pruned FFT in O(n*log(k)) Numerics fftw	5	862	November 6, 2022
Performance advice needed Performance fftw	17	1441	January 17, 2020
Sieving for Bsmooth values Performance	15	479	March 9, 2023

Optimal Power of N for FFTW

Related topics