Improve good_size and export to python

This improves the algorithm for good_size. The main observation is that division by 2 is cheap, so we can alternate between multiplying by 3 and dividing by 2 to reduce the search space to only numbers near n. This also adds an early return when n matches a composite number. You can play around with the micro-benchmarks here (this is good_size2).

This also adds a variant for real transforms with 5-smooth numbers and exports both of them to python as a single function.

changed the description

Fancy stuff, thanks!

Are you testing with very long 1D transforms, or how did this function pop up on your radar?

If we wanted to really find the fastest transforms, we would in principle not check for the smallest fast length, but for the "reasonably small" fast length with the lowest FFT cost (which scales roughly as "length times (sum of prime factors of length)", but this is probably too expensive to determine.

merged

mentioned in commit 6f1bba7d

For example: length 121 vs. 125

I'm looking into updating scipy.ftt.next_fast_len with the new prime factors but a brute-force search in python was very slow. I found this special case for factors 2&3 on a stack overflow post (that I can't seem to find any more) but in the end decided it really needed to be in C++ for the speed.

Searching for lowest FFT cost sounds like a great idea though. I just tried with lengths 12100 and 12500; the longer transform was ~25% faster, matching that estimate pretty well. Since this algorithm always searches for the smallest prime factors first, I think that we could use the exact same loops but compare cost estimates instead of bestfac directly. I might give that a shot.

mentioned in merge request !18