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

[Laurent Bonnaud <bonnaud at irisa dot fr>]

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

I retried this code with egcs-2.91.14 (980315) and now it compiles fine
wihtout even having to use -ftemplate-depth-???.  Thank you for this
great improvement !  However, the result is not always what is
expected:

 1 is prime
 2 is prime
 3 is prime
 4 is not prime
 5 is prime
 6 is not prime
 7 is prime
 8 is not prime
 9 is not prime
10 is not prime
10 is prime
11 is prime
12 is prime
13 is not prime
14 is prime

With KCC i get the correct result :

 1 is prime
 2 is prime
 3 is prime
 4 is not prime
 5 is prime
 6 is not prime
 7 is prime
 8 is not prime
 9 is not prime
10 is not prime
10 is not prime
11 is prime
12 is not prime
13 is prime
14 is not prime

The result begins to be different when the Decimal<> template is used.
So the result for 10 is right when coded as 'ten', but not when coded
as 'Decimal<one,zero>'.  I'm reposting the updated test case below.

-- 
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 "is not prime"; }
template<> char *output(one) { return "is prime"; }

main() {
  printf("%2d %s\n",1,output(Prime<one>::value()));
  printf("%2d %s\n",2,output(Prime<two>::value()));
  printf("%2d %s\n",3,output(Prime<three>::value()));
  printf("%2d %s\n",4,output(Prime<four>::value()));
  printf("%2d %s\n",5,output(Prime<five>::value()));
  printf("%2d %s\n",6,output(Prime<six>::value()));
  printf("%2d %s\n",7,output(Prime<seven>::value()));
  printf("%2d %s\n",8,output(Prime<eight>::value()));
  printf("%2d %s\n",9,output(Prime<nine>::value()));
  printf("%2d %s\n",10,output(Prime<ten>::value()));
  printf("%2d %s\n",10,output(Prime<Decimal<one,zero>::value>::value()));
  printf("%2d %s\n",11,output(Prime<Decimal<one,one>::value>::value()));
  printf("%2d %s\n",12,output(Prime<Decimal<one,two>::value>::value()));
  printf("%2d %s\n",13,output(Prime<Decimal<one,three>::value>::value()));
  printf("%2d %s\n",14,output(Prime<Decimal<one,four>::value>::value()));
}