fft_good
|
fft_good(n)
returns the smallest number of the form 2^x*3^y*5^z greater
than or equal to n. An fft of this length will be much faster
than a number with larger prime factors; the speed difference
can be an order of magnitude or more.
For n>100, the worst cases result in a little over a 11% increase
in n; for n>1000, the worst are a bit over 6%; still larger n are
better yet. The median increase for n<=10000 is about 1.5%.
|