Trying to compile D. Piponi's template based primality test

[Laurent Bonnaud <bonnaud at irisa dot fr>]

Hi,

i'm trying to compile the attached program, but it fails because the
template instantiation depth is too deep.  The original program tests
the number '13'.  KCC can compile it in a few seconds and with 4MB of
memory.  With egcs, i replaced '13' with '1', used
-ftemplate-depth-1000 and it still does not compile.  The compilation
lasts several minutes, and cc1plus uses 80MB of memory.  I guess that
egcs gets caught in a loop, where it should not.  Does anybody know if
this is a bug a egcs, or how i could modify the program to work ?

Thank you,

-- 
Laurent.

//
// A C++ program to test for the primality of the number 13
//
// It has the curious property that it does no arithmetic
// but uses only the template mechanism and class derivation
// to achieve its result. It starts at the most basic axioms
// of arithmetic starting with the definition of zero and
// its successors...
//
// You'll need a good C++ compiler.
//
// (c) D Piponi (But copy it as much as you like if you credit me)
//

template<class V> struct Value { typedef V value; };
struct zero
        : public Value<zero> { };
template<class C> struct S
        : public Value<S<C> > { typedef C predecessor; };

typedef S<zero> one;
typedef S<one> two;
typedef S<two> three;
typedef S<three> four;
typedef S<four> five;
typedef S<five> six;
typedef S<six> seven;
typedef S<seven> eight;
typedef S<eight> nine;
typedef S<nine> ten;

template<class C,class D> struct plus
        : public S<plus<C,typename D::predecessor> > { };
template<class C> struct plus<C,zero>
        : public C { };

template<class C,class D> struct minus
        : public minus<C,typename D::predecessor>::predecessor { };
template<class C> struct minus<C,zero>
        : public C { };

template<class C,class D> struct times
        : public plus<C,typename times<C,typename D::predecessor>::value> { };
template<class C> struct times<C,zero>
        : public zero { };

template<class C,class D> struct ge
        : public ge<typename C::predecessor,typename D::predecessor> { };
template<class C> struct ge<C,zero>
        : public one { };
template<class C> struct ge<zero,C>
        : public zero { };
template<> struct ge<zero,zero>
        : public one { };

template<class C,class D,class E = S<S<zero> > > struct Divisible { };
template<class C,class D> struct Divisible<C,D,S<S<zero> > >
        : public Divisible<C,D,typename ge<C,D>::value> { };
template<class C,class D> struct Divisible<C,D,zero>
        : public zero { };
template<class C> struct Divisible<zero,C,zero>
        : public one { };
template<class C,class D> struct Divisible<C,D,S<zero> >
        : public Divisible<typename minus<C,D>::value,D> { };

template<class C,class D = two,class S = zero,class E = zero,class F = zero> struct Prime { };
template<class C,class D> struct Prime<C,D,zero,zero,zero>
        : public Prime<C,D,one,zero,typename ge<D,C>::value> { };
template<class C,class D> struct Prime<C,D,one,zero,zero>
        : public Prime<C,S<D>,zero,typename Divisible<C,D>::value,zero> { };
template<class C,class D> struct Prime<C,D,zero,one,zero>
        : public zero { };
template<class C,class D> struct Prime<C,D,one,zero,one>
        : public one { };

template<class C,class D> struct Decimal
        : public plus<times<ten,C>::value,D> { };

#include <stdio.h>

template<class C> char *output(C);
template<> char *output(zero) { return "No"; }
template<> char *output(one) { return "Yes"; }

main() {
  //puts(output(Prime<Decimal<one,three>::value>::value()));
  puts(output(Prime<one>::value()));
}