Python code for computing fast FFT sizes.

fftsize.py

#!/usr/bin/env python
from __future__ import print_function
import numpy as np
from numpy import log, ceil


def nextpower(n, base=2.0):
    """Return the next integral power of two greater than the given number.
    Specifically, return m such that
        m >= n
        m == 2**x
    where x is an integer. Use base argument to specify a base other than 2.
    This is useful for ensuring fast FFT sizes.
    """
    x = base**ceil(log(n) / log(base))
    if type(n) == np.ndarray:
        return np.asarray(x, dtype=int)
    else:
        return int(x)


def nextfastpower(n):
    """Return the next integral power of small factors greater than the given
    number.  Specifically, return m such that
        m >= n
        m == 2**x * 3**y * 5**z
    where x, y, and z are integers.
    This is useful for ensuring fast FFT sizes.
    """
    if n < 7:
        return max(n, 1)
    # x, y, and z are all bounded from above by the formula of nextpower.
    # Compute all possible combinations for powers of 3 and 5.
    # (Not too many for reasonable FFT sizes.)

    def power_series(x, base):
        nmax = int(ceil(log(x) / log(base)))
        return np.logspace(0.0, nmax, num=nmax+1, base=base)
    n35 = np.outer(power_series(n, 3.0), power_series(n, 5.0))
    n35 = n35[n35 <= n]
    # Lump the powers of 3 and 5 together and solve for the powers of 2.
    n2 = nextpower(n / n35)
    return int(min(n2 * n35))


def test():
    primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
              61, 67, 71, 73, 79, 83, 89, 97)
    others = (15, 16, 30)
    for n in primes + others:
        print("nextpowtwo (%d) = %d" % (n, nextpower(n)))
        print("nextfastpower (%d) = %d" % (n, nextfastpower(n)))
        print()


if __name__ == '__main__':
    test()