primePaddingHeuristic function

bool primePaddingHeuristic(
  1. int n
)

Returns whether padding the PrimeFFT to a power of two size is likely to be faster than not padding it.

Experimentally, padding is usually a win when the largest prime factor of n - 1 is greater than 5. We also special case a few small sizes where this simple heuristic is wrong.

Implementation

bool primePaddingHeuristic(int n) {
  if (n == 31 || n == 61 || n == 101 || n == 241 || n == 251) return true;
  return largestPrimeFactorIsAbove(n - 1, 5);
}