scipy/scipy — pull request #3670 by endolith (2014-05-19 14:48:52+00:00)
Title: ENH: Small speedup of FFT size check

Use a bit-twiddling power of 2 check instead of repeatedly dividing by 2

```
In [87]: n = 128

In [88]: a = rand(n)

In [89]: timeit _is_smooth_size(n)
1000000 loops, best of 3: 1.65 us per loop

In [90]: timeit _is_smooth_size_fast(n)
1000000 loops, best of 3: 545 ns per loop

In [91]: timeit fft(a)
1 loops, best of 3: 6.54 us per loop
```

So 6.54+1.65 vs 6.54+0.5 = 14% speedup for small sizes?

```
n = 2**37 * 3**44 * 5**42

timeit _is_safe_size(n)
10000 loops, best of 3: 86.1 µs per loop

timeit _is_safe_size_fast(n)
10000 loops, best of 3: 61.3 µs per loop

n = 32

timeit _is_safe_size(n)
1000000 loops, best of 3: 1.85 µs per loop

timeit _is_safe_size_fast(n)
1000000 loops, best of 3: 899 ns per loop
```