Quelle est la fonction de vérification principale récursive la plus efficace connue?

J’expérimentais avec la méta-programmation à ce point:

// comstackd on Ubuntu 13.04 with: // clang++ -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl comstack-time-primes.cpp -o comstack-time-primes // assembly output with: // clang++ -S -mllvm --x86-asm-syntax=intel -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl comstack-time-primes.cpp -o comstack-time-primes.asm #include  #include  template constexpr bool is_prime(T number, T limit, T counter) { return counter >= limit ? number % limit != 0 : number % counter ? is_prime(number, number / counter, counter + 2) : false; } template constexpr bool is_prime(T n) { return n == 2 || n == 3 || n == 5 ? true : n <= 1 || n % 2 == 0 ? false : is_prime(n, n / 3, T{3}); } template struct print_below; template struct print_below { inline static void primes() { std::cout << 2; } }; template struct print_below { inline static void primes() { print_below::primes(); constexpr bool is_n_prime = is_prime(n); if(is_n_prime) std::cout << ", " << n; } }; template  struct primes { static const std::array cache; }; template  struct append_param; template  struct append_param<T, primes, R> { using primes = primes; }; template  struct indexer : append_param<size_t, typename indexer::primes, N - 1> {}; template  struct indexer { using primes = primes; }; template  const std::array primes::cache = {{ is_prime(N)... }}; int main() { std::cout << "Some primes: \n"; print_below::primes(); std::cout << std::endl; const auto &primes_cache = indexer::primes::cache; for(size_t i = 1; i < primes_cache.size(); ++i) std::cout << i << (primes_cache[i] ? " is " : " is not ") << "prime" << std::endl; } 

Maintenant, je me demande s’il existe un meilleur algorithme récursif pour is_prime qui peut être mis dans une fonction constexpr .

Y at-il quelque chose de beaucoup mieux que cela?

  • Condition: il doit être récursif.
  • Souhaitable: constexpr dans une fonction constexpr .

Oui.

Tout d’abord, l’une de vos principales limites sera votre profondeur de récursion. Le vôtre revient une fois pour chaque nombre impair de 3 à sqrt(N) . Avec une limite de récursivité de ~ 1000, cela signifie que vous ne pourrez gérer que des nombres allant jusqu’à 1 million. Vous devez réduire le nombre de récursions que vous faites.

Une façon de faire est de faire une recherche par division des facteurs de votre nombre N Avec un peu de travail, vous pouvez étendre cela à une limite de l’ordre de 2^1000 (autrement dit, d’autres choses que la limite de récursivité l’empêcheront de fonctionner en premier).

Deuxièmement, au lieu de vérifier chaque nombre impair, vérifiez 6 mod 1 et 5, avec un cas spécial pour vérifier 2/3/5 au début. Des motifs à plus longue plage peuvent être utilisés aussi bien qu’un rayon de 6.

Troisièmement, il existe des tests de primalité probabilistes suffisamment fiables pour que leur utilisation soit la bonne réponse. Vous pouvez probablement créer un tableau codé en dur des nombres pour lesquels le test a échoué, vérifier ce tableau et le faire autrement, et rendre votre limite supérieure beaucoup, beaucoup plus élevée que ce que vous pouvez pratiquement faire autrement.

Un autre problème de votre conception réside dans le fait qu’il teste les nombres premiers les uns après les autres: idéalement, vous devez créer un tableau des nombres premiers et les utiliser pour vous aider dans vos tests des nombres premiers. Certains compilateurs mémoriseront les résultats précédents, vous pouvez envisager de l’exploiter.