Optimal Power of N for FFTW

Specific Domains Signal and Image Processing
1

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.

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