## 17.4 Using Induction Variables

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 3, we write a loop in which a variable 3 iterates from one to 3 until its square is equal to or greater than 3. This value 3 is our square root of 3. If we formulate this problem in ordinary C++, it looks as follows:

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

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 computesqrt(N)via iterationtemplate <int N, int I=1> class Sqrt { public: enum { result = (I*I<N) ? Sqrt<N,I+1>::result : I }; }; //partial specialization to end the iterationtemplate<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 ^{2 }`(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

^{2 }`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 resulttemplate<int N> class Value { public: enum { result = N }; }; //template to computesqrt(N)via iterationtemplate <int N, int I=1> class Sqrt { public: //instantiate next step or result type as branchtypedef typename IfThenElse<(I*I<N), Sqrt<N,I+1>, Value<I> >::ResultT SubT; //use the result of branch typeenum { 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_{2}(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).