JuliaLang/julia — pull request #981 by timholy (2012-06-27 10:31:32+00:00)
Title: RFC: good names for utility functions for efficient FFTs

FFTs are most efficient if the length is a product of powers of small primes. nextpow2 allows you to compute the next power-of-two, and is a good choice for 1 dimensional FFTs. However, for 3-dimensional FFTs, using nextpow2 could result in an array that contains almost 8-fold more elements, and in this case the efficiency of the FFT algorithm usually does not compensate for the extra elements.

The utilities in this commit allow you to define something like "nextpowb", where b is a list of possible factors. Example:

# compute all integers that are 2^l*3^m*5^n, up to the first that is >= 1025
p = powers([2,3,5],1025)
# find a size appropriate for a vector of 220 elements
s = nextsize(220, p)

Using [2,3,5], up to x=10,000 the ratio of nextsize(x,p)/x is never bigger than 1.1538, and has a median value of 1.0124. Consequently, in the worst-case scenario a 3d FFT will require only 1.5362-fold more elements, a very significant savings over using nextpow2. "powers" is also reasonably fast, requiring about 0.023 s up to x=10^5 (using [2,3,5]), about the largest size you could imagine being relevant for multidimensional FFTs. And you only need to call it once, even if you have many FFTs to compute.

In addition to any discussion re the intent, algorithms, etc, I would appreciate feedback about the choice of names! I'd kind of like to make this more discoverable, e.g., by starting a function name with "nextpow", but the interface is a little different (in particular, you likely want to pre-compute p, rather than nextpowb(220, [2,3,5]) on each iteration).

Thoughts?