Square Root computation

Tips and Tricks

// The recursion proceeds using a binary search technique

// (often called method of bisection). Inside the template,

// we compute if the result is in the first or second half

// of the range between LO and HI. This case differentiation

// is done using the conditional operator ?:. if mid^2 is

// greater than N, we continue to search in the first half.

// if mid^2 is less or equal to N, we use the same template

// for the second half again.

 // The specialization that ends the recursive process is

// when LO and HI have the same value M, which is the final result.

 // primary template to compute sqrt(N)

template<intN, intLO=1, intHI=N>

classSqrt

{

public:

// compute the midpoint, rounded up

enum {mid=(LO+HI+1)/2};

// search a not too large value in the halved interval

enum {result = (N<mid*mid) ? Sqrt<N,LO,mid-1>::result

                                            : Sqrt<N,mid,HI>::result};

};

// partial specialization for the case when LO equal HI

template<intN, intM>

classSqrt<N,M,M>

{

public:

enum {result=M};

};

 

clients and partners

Autolog