已知最有效的尾递归素数验证功能是什么? [英] What's the most efficient tail recursive prime verification function known?

问题描述

我现在正在尝试元编程:

I was experimenting with meta programming to this point:

// 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函数中.

Now I'm wondering whether there's a better tail recursive algorithm for is_prime that can be put in a constexpr function.

有什么比这更好的了吗?

Is there anything much better than this?

• 要求:它必须是尾递归的.
• 理想:适合constexpr函数.

• Requirement: It must be tail recursive.
• Desirable: To fit in a constexpr function.

推荐答案

是.

首先，您的主要限制之一是递归深度限制.您的每个从3到sqrt(N)的奇数都重复一次.递归限制为〜1000，这意味着您最多只能处理100万个数字.您需要减少正在执行的递归量.

First of all, one of your main limits will be your recursion depth limit. Yours recurses once for every odd number from 3 to sqrt(N). With a ~1000 recursion limit, it means you'll only be able to handle numbers up to 1 million. You need to reduce the amount of recursion you are doing.

一种方法是对您的数字N的因数进行分治法搜索.通过一些工作，您可以将其扩展到2^1000的数量级限制(即，除递归限制外，其他情况将使其首先失效).

A way to do this is to do a divide-and-conquer search for the factors of your number N. With a bit of work, you can extend this to a limit on the order of 2^1000 (ie, other things, besides recursion limit, will make it fail to work first).

第二，而不是检查每个奇数，而是检查6 mod 1和5，特殊情况是在开始时检查2/3/5.不仅可以使用半径为6的半径，还可以使用更长距离的图案.

Second, instead of checking every odd number, check 6 mod 1 and 5, with a special case to check 2/3/5 at the start. Longer ranged patterns can be used as well than just a radius of 6.

第三，有一些概率性素性测试足够可靠，以至于使用它们是正确的答案.您可能会为测试失败的数字建立一个硬编码表，对照该表进行检查，否则进行测试，并使您的上限大大提高，远高于实际无法实现的水平.

Third, there are probabilistic primality tests that are sufficiently reliable that using them is the right answer. You could probably build a hard coded table of the numbers for which the test fails, check against that table, and do the tests otherwise, and make your upper limit much, much higher than what you can practically do otherwise.

设计的另一个问题是它一次测试一个素数:理想情况下，您应该建立一个素数表，并使用这些表来帮助您进行素数测试.一些编译器会记录以前的结果，您可以研究利用它.

Another issue with your design is that it tests for primes one at a time: ideally, you should build up a table of primes and use those to help with your prime testing. Some compilers will do memoization of previous results, you can look into exploiting that.

这篇关于已知最有效的尾递归素数验证功能是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！