已知最高效的尾遞歸素數驗證函數是什麼？

Question

我和元編程嘗試了這一點：

// compiled on Ubuntu 13.04 with: 
// clang++ -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes.cpp -o compile-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 compile-time-primes.cpp -o compile-time-primes.asm 

#include <array> 
#include <iostream> 

template<typename T> 
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<typename T> 
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<size_t n> 
struct print_below; 

template<> struct print_below<2> { inline static void primes() { std::cout << 2; } }; 
template<size_t n> 
struct print_below 
{ 
    inline static void primes() 
    { 
     print_below<n - 1>::primes(); 
     constexpr bool is_n_prime = is_prime(n); 
     if(is_n_prime) 
      std::cout << ", " << n; 
    } 
}; 

template <typename T, T... N> 
struct primes { static const std::array<bool, sizeof...(N)> cache; }; 

template <typename T, typename L, T R> 
struct append_param; 

template <typename T, T... L, T R> 
struct append_param<T, primes<T, L...>, R> { using primes = primes<T, L..., R>; }; 

template <size_t N> 
struct indexer : append_param<size_t, typename indexer<N - 1>::primes, N - 1> {}; 

template <> 
struct indexer<0> { using primes = primes<size_t>; }; 

template <typename T, T... N> 
const std::array<bool, sizeof...(N)> primes<T, N...>::cache = {{ is_prime(N)... }}; 

int main() 
{ 
    std::cout << "Some primes: \n"; 
    print_below<8000>::primes(); 
    std::cout << std::endl; 

    const auto &primes_cache = indexer<1000>::primes::cache; 

    for(size_t i = 1; i < primes_cache.size(); ++i) 
     std::cout << i << (primes_cache[i] ? " is " : " is not ") << "prime" << std::endl; 
} 

現在我想知道是否有用於is_prime更好尾遞歸算法，它可以放在一個constexpr功能。

有什麼比這更好的嗎？

• 要求：它必須是尾遞歸的。
• 合意：適合constexpr功能。

Answer 1

是的。

首先，您的主要限制之一將是您的遞歸深度限制。對於從3到sqrt(N)的每個奇數，您都會遞歸一次。有了〜1000遞歸限制，這意味着你只能處理高達100萬的數字。你需要減少你正在做的遞歸量。

一種方法是對您的號碼N進行分數和征服搜索。通過一些工作，您可以將其擴展到2^1000的限制（即，除了遞歸限制之外，其他事情將使其無法首先工作）。其次，不是檢查每個奇數，而是檢查6模1和5，用特殊情況在開始時檢查2/3/5。可以使用更遠距離的模式以及半徑僅爲6.

第三，有概率的素性測試足夠可靠，使用它們是正確的答案。你也許可以建立一個測試失敗的硬編碼表格，檢查這個表格，然後進行測試，並且將你的上限設置得很多，遠遠高於你實際上可以做的其他工作。

您的設計的另一個問題是它一次測試一個質數：理想情況下，您應該建立一個質數表並使用它們來幫助進行主要測試。有些編譯器會記錄以前的結果，你可以考慮利用它。