n-te Primzahl mit TMP



  • Heyo,

    weil mir langweilig ist, habe ich mich an Projekt Euler versucht, jedoch bloss mit reiner TMP. Problem 7 gibt mir ein wenig zu beissen; die Aufgabe fragt nach der 10001ten Primzahl. Hier ist mein naiver Ansatz mit trial division:

    template<unsigned int x, unsigned int i = 2, bool rem = x % i, bool stop = (i * 2 > x)>
    struct is_prime
    {
    	static constexpr bool v = is_prime<x, i + 1 + (i >= 3)>::v;
    };
    template<unsigned int x, unsigned int i, bool stop>
    struct is_prime<x, i, false, stop>
    {
    	static constexpr bool v = false;
    };
    template<unsigned int x, unsigned int i>
    struct is_prime<x, i, true, true>
    {
    	static constexpr bool v = true;
    };
    template<unsigned int i>
    struct is_prime<1, i, true, true>
    {
    	static constexpr bool v = false;
    };
    template<unsigned int i>
    struct is_prime<2, i, false, true>
    {
    	static constexpr bool v = true;
    };
    
    template<unsigned int n, unsigned int x = 1, unsigned int i = 0>
    struct nth_prime
    {
    	static constexpr unsigned int v = nth_prime<n, x + 1 + (x >= 3), i + is_prime<x + 1 + (x >= 3)>::v>::v;
    };
    template<unsigned int x, unsigned int i>
    struct nth_prime<0, x, i>;
    template<unsigned int n, unsigned int x>
    struct nth_prime<n, x, n>
    {
    	static constexpr unsigned int v = x;
    };
    
    int main()
    {
    	std::cout << nth_prime<10001>::v << '\n';
    }
    

    Leider segfaulted GCC nach einiger Zeit, für kleine n scheint das Programm jedoch zu stimmen.
    Hat jemand eine Idee, wie man das sonst machen könnte? An Siebe habe ich natürlich als erstes gedacht, jedoch war mir schleierhaft, wie ich sie mit TMP implementieren kann.

    LG



  • template <unsigned x>
    struct nth_prime 
    {};
    
    template <>
    struct nth_prime <10001>
    {
        static constexpr const unsigned value = 104743;
    }
    

    Ansonsten viel Glück...

    (Randinfo: Die standard maximale Instanziierungstiefe des gcc ist 900).



  • 5cript schrieb:

    constexpr const

    Nein.



  • Ok, ich habe nun das Sieb des Eratosthenes in TMP implementiert. Für kleine N (≤ 3000) funktioniert es auch, aber bei 105000 hat es keine Chance.

    #include <iostream>
    #include <cstdint>
    #include <limits>
    
    template<unsigned int x, unsigned int i = (x + 1) / 2, bool done = (i * i <= x) && (x < (i + 1) * (i + 1))>
    struct sqrt
    {
    	static constexpr unsigned int v = sqrt<x, (i + x / i) / 2>::v;
    };
    template<unsigned int x, unsigned int i>
    struct sqrt<x, i, true>
    {
    	static constexpr unsigned int v = i;
    };
    
    using uint_t = std::uint64_t;
    static constexpr std::size_t digits = std::numeric_limits<uint_t>::digits;
    
    template<uint_t... bits>
    struct bitset
    {
    	static constexpr std::size_t size = sizeof...(bits) * digits;
    };
    
    template<typename T, typename U>
    struct merge;
    template<uint_t... l_bits, uint_t... r_bits>
    struct merge<bitset<l_bits...>, bitset<r_bits...>>
    {
    	using t = bitset<l_bits..., r_bits...>;
    };
    
    template<unsigned int i, uint_t x>
    struct make_bitset
    {
    	using t = typename merge<typename make_bitset<i / 2, x>::t, typename make_bitset<(i + 1) / 2, x>::t>::t;
    };
    template<uint_t x>
    struct make_bitset<0, x>
    {
    	using t = bitset<>;
    };
    template<uint_t x>
    struct make_bitset<1, x>
    {
    	using t = bitset<x>;
    };
    
    template<typename T, unsigned int i, bool there = (i < digits)>
    struct get_bit;
    template<uint_t head, uint_t... tail, unsigned int i>
    struct get_bit<bitset<head, tail...>, i, false>
    {
    	static constexpr bool v = get_bit<bitset<tail...>, i - digits>::v;
    };
    template<uint_t head, uint_t... tail, unsigned int i>
    struct get_bit<bitset<head, tail...>, i, true>
    {
    	static constexpr bool v = head & (uint_t{ 1 } << i);
    };
    
    template<typename T, unsigned int i, bool value, bool there = (i < digits)>
    struct set_bit;
    template<uint_t head, uint_t... tail, unsigned int i, bool value>
    struct set_bit<bitset<head, tail...>, i, value, false>
    {
    	using t = typename merge<bitset<head>, typename set_bit<bitset<tail...>, i - digits, value>::t>::t;
    };
    template<uint_t head, uint_t... tail, unsigned int i, bool value>
    struct set_bit<bitset<head, tail...>, i, value, true>
    {
    	static constexpr uint_t mask = uint_t{ 1 } << i;
    	using t = bitset<value ? head | mask : head & ~mask, tail...>;
    };
    
    template<typename T, unsigned int x, unsigned int i = 2 * x, bool stop = (i >= T::size)>
    struct mark_multiples
    {
    	using t = typename mark_multiples<typename set_bit<T, i, false>::t, x, i + x>::t;
    };
    template<typename T, unsigned int x, unsigned int i>
    struct mark_multiples<T, x, i, true>
    {
    	using t = T;
    };
    
    template<bool condition, typename T, unsigned int x>
    struct conditionally_mark_multiples
    {
    	using t = typename mark_multiples<T, x>::t;
    };
    template<typename T, unsigned int x>
    struct conditionally_mark_multiples<false, T, x>
    {
    	using t = T;
    };
    
    template<typename T, unsigned int i = 2, bool stop = (i > sqrt<T::size>::v)>
    struct eratosthenes
    {
    	using t = T;
    };
    template<typename T, unsigned int i>
    struct eratosthenes<T, i, false>
    {
    	using t = typename eratosthenes<typename conditionally_mark_multiples<get_bit<T, i>::v, T, i>::t, i + 1 + (i >= 3)>::t;
    };
    
    template<typename T, unsigned int n, unsigned int k = 0, unsigned int i = 0>
    struct get_nth
    {
    	static constexpr unsigned int v = get_nth<T, n, k + get_bit<T, i>::v, i + 1>::v;
    };
    template<typename T, unsigned int n, unsigned int i>
    struct get_nth<T, n, n, i>
    {
    	static constexpr unsigned int v = i - 1;
    };
    
    int main()
    {
    	//static constexpr std::size_t N = 105000;
    	static constexpr std::size_t N = 3000;
    	using t0 = make_bitset<(N - 1) / digits + 1, static_cast<uint_t>(-1)>::t;
    	using t1 = set_bit<t0, 0, false>::t;
    	using t2 = set_bit<t1, 1, false>::t;
    	using t3 = eratosthenes<t2>::t;
    	//std::cout << get_nth<t3, 10001>::v << '\n';
    	std::cout << get_nth<t3, 400>::v << '\n';
    }
    

    Ich kann mir sehr gut vorstellen, dass bei set_bit die meisten Instantiierungen verloren gehen. Hat jemand eine Idee, wie man das besser machen könnte?



  • Wenn es nur darum gehen sollte, Primzahlen zur Compilierzeit mit dem Sieb zu berechnen, könnte man C++14-constexpr-Funktionen nehmen. Das erspart die Rekursion und damit die limitierte Rekursionstiefe.



  • Fytch schrieb:

    5cript schrieb:

    constexpr const

    Nein.

    Das habe ich mir aufgrund von VC++ angewöhnt. Ich kann nicht mehr sagen warum, aber entweder lag es an einem ICE oder irgendwelchen komischen bugs.
    Aber VC ist eh broken.

    EDIT: Bzgl Rekursionstiefe wäre selbst eine O(n) Laufzeit zu schlecht. Es müsste schon maximal logarithmisch sein. Ich glaube nicht, dass das möglich ist. Erst recht nicht ohne folds.
    Ja constexpr functions würde ich heranziehen und auch boost HANA.


Log in to reply