Skip to content

Instantly share code, notes, and snippets.

@bhawkins
Last active March 8, 2020 19:21
Show Gist options
  • Save bhawkins/4479607 to your computer and use it in GitHub Desktop.
Save bhawkins/4479607 to your computer and use it in GitHub Desktop.
Python code for computing fast FFT sizes.
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment