August 20, 2006

以 C++ template meta-programming 來實現 Sieve of Eratosthenes

Peter Simons 做了一個展示,用 C++ template meta-programming 來實現 [Sieve of Eratosthenes],可參考 [prime-sieve.cc]。[Sieve of Eratosthenes] 是古典數學中用以求質數相當經典且簡單的途徑,不需要太多解釋,直接觀看 Wikipedia 的圖解就可知悉其演算法:

而,運用 C++ template meta-programming 可用更直覺的方式來「描述」該演算法,試看以下程式列表:
//////////////////////////////////////////////////
// Alorithm to create [i..n]
//////////////////////////////////////////////////

template<unsigned int i, unsigned int n>
struct makeIntList
{
        typedef Typelist< IntType<i>, typename makeIntList<i+1, n>::Result > Result;
};
template<unsigned int n>
struct makeIntList<n, n>
{
        typedef Typelist< IntType<n>, NullType > Result;
};
//////////////////////////////////////////////////
// The Sieve of Erathostenes
//////////////////////////////////////////////////

template<unsigned int i, typename TList>
struct sieveOne;
template<unsigned int i, typename x, typename xs>
struct sieveOne< i, Typelist<x,xs> >
{
        typedef typename Select<

                x::value % i != 0,
                Typelist< x, typename sieveOne<i, xs>::Result >,
                typename sieveOne<i, xs>::Result
                        >::Result    Result;
};
template<unsigned int i>
struct sieveOne<i, NullType>
{
        typedef NullType Result;
};
template<typename TList>
struct sieveAll;
template<typename x, typename xs>
struct sieveAll< Typelist<x,xs> >
{
        typedef Typelist<
                x,
                typename sieveAll<typename sieveOne<x::value, xs>::Result>::Result
                        >     Result;
};
template<>
struct sieveAll<NullType>
{
        typedef NullType Result;
};
template<unsigned int n>
struct primeSieve
{
        typedef typename sieveAll<typename makeIntList<2,n>::Result>::Result Result;
};
整個演算法被包裝成 template object,其中可看到試除的過程,最後我們再設計可一一讀取 Result 的 iterator。當代入[2..20],可得以下輸出:
    $ ./prim-sieve 
    Finding prime numbers in [2..20]:
    2 3 5 7 11 13 17 19
    
令人驚豔的優雅!
由 jserv 發表於 August 20, 2006 02:50 PM
迴響

他似乎沒有「設計可一一讀取 Result 的 Iterator」,
而只是「將 Result 一一寫入 Output Iterator」而已。

Palatis 發表於 September 16, 2006 03:52 AM