17.4 Using Induction Variables

Ru-Brd

You may argue that the way the metaprogram is written in the previous example looks rather complicated. And you may wonder whether you have learned something you can use whenever you have a problem to solve by a metaprogram. So, let's look for a more "naive" and maybe "more iterative" implementation of a metaprogram that computes the square root.

A "naive iterative algorithm" can be formulated as follows : To compute the square root of a given value N , we write a loop in which a variable I iterates from one to N until its square is equal to or greater than N . This value I is our square root of N . If we formulate this problem in ordinary C++, it looks as follows:

 int I;  for (I=1; I*I<N; ++I) {      ;  }  //  I  now contains the square root of  N 

However, as a metaprogram we have to formulate this loop in a recursive way, and we need an end criterion to end the recursion. As a result, an implementation of this loop as a metaprogram looks as follows:

  // meta/sqrt3.hpp  #ifndef SQRT_HPP  #define SQRT_HPP  // primary template to compute  sqrt(N)  via iteration  template <int N, int I=1>  class Sqrt {    public:      enum { result = (I*I<N) ? Sqrt<N,I+1>::result                              : I };  };  // partial specialization to end the iteration  template<int N>  class Sqrt<N,N> {    public:      enum { result = N };  };  #endif  // SQRT_HPP  

We loop by "iterating" I over Sqrt<N,I> . As long as I*I<N yields true , we use the result of the next iteration Sqrt<N,I+1>::result as result. Otherwise I is our result.

For example, if we evaluate Sqrt<16> this gets expanded to Sqrt<16,1> . Thus, we start an iteration with one as a value of the so-called induction variable I . Now, as long as I ² (that is I*I ) is less than N , we use the next iteration value by computing Sqrt<N,I+1>::result . When I ² is equal to or greater than N we know that I is the result .

You may wonder why we need a template specialization to end the recursion because the first template always, sooner or later, finds I as the result, which seems to end the recursion. Again, this is the effect of the instantiation of both branches of operator ?: , which was discussed in the previous section. Thus, the compiler computes the result of Sqrt<4> by instantiating as follows:

• Step 1:

   result = (1*1<4) ? Sqrt<4,2>::result                   : 1 

• Step 2:

   result = (1*1<4) ? (2*2<4) ? Sqrt<4,3>::result                             : 2                   : 1 

• Step 3:

   result = (1*1<4) ? (2*2<4) ? (3*3<4) ? Sqrt<4,4>::result                                       : 3                             : 2                   : 1 

• Step 4:

   result = (1*1<4) ? (2*2<4) ? (3*3<4) ? 4                                       : 3                             : 2                   : 1 

Although we find the result in step 2, the compiler instantiates until we find a step that ends the recursion with a specialization. Without the specialization, the compiler would continue to instantiate until internal compiler limits are reached.

Again, the application of the IfThenElse template solves the problem:

  // meta/sqrt4.hpp  #ifndef SQRT_HPP  #define SQRT_HPP  #include "ifthenelse.hpp"  // template to yield template argument as result  template<int N>  class Value {    public:      enum { result = N };  };  // template to compute  sqrt(N)  via iteration  template <int N, int I=1>  class Sqrt {    public:  // instantiate next step or result type as branch  typedef typename IfThenElse<(I*I<N),                                  Sqrt<N,I+1>,                                  Value<I>                                 >::ResultT              SubT;  // use the result of branch type  enum { result = SubT::result };  };  #endif  // SQRT_HPP  

Instead of the end criterion we use a Value<> template that returns the value of the template argument as result .

Again, using IfThenElse<> leads to a number of instantiations that is proportional to log ₂ ( N ) instead of N . This is a very significant reduction in the cost of metaprogramming. And for compilers with template instantiation limits, this means that you can evaluate the square root of much larger values. If your compiler supports up to 64 nested instantiations, for example, you can process the square root of up to 4096 (instead of up to 64).

The output of the "iterative" Sqrt templates is as follows:

 Sqrt<16>::result = 4  Sqrt<25>::result = 5  Sqrt<42>::result = 7  Sqrt<1>::result =  1 

Note that this implementation produces the integer square root rounded up for simplicity (the square root of 42 is produced as 7 instead of 6).

Ru-Brd