[Click here for a PDF of this post with nicer formatting]

In [1] is a rather mysterious looking constant expression formula for an integer square root. This is a function that returns the smallest integer for which the square is less than the value to take the root of. Check out the black magic he used

// Stroustrup 10.4:  constexpr capable integer square root function
constexpr int isqrt_helper( int sq, int d, int n )
{
	return sq <= n ? isqrt_helper( sq + d, d + 2, n ) : d ;
}

constexpr int isqrt( int n )
{
	return isqrt_helper( 1, 3, n )/2 - 1 ;
}

The point of this construction was really to illustrate that it allows complex expressions to be used as compile time constants. I wonder at what point various compilers will give up trying to evaluate such expressions?

Let’s take this apart a bit.

Consider the first few values of \( n > 0 \).

• \( n = 0 \). Here we have a call to \( \textrm{isqrt_helper}( 1, 3, 0 ) \) so the \( 1 \le 0 \) predicate is false, and the return value is just \( 3 \).

  For that value we have (using integer arithmetic):

  \begin{equation}\label{eqn:isqrt:20}
  \frac{3}{2} – 1 = 0,
  \end{equation}

  as desired.

• \( n = 1 \). Here we have a call to \( \textrm{isqrt_helper}( 1, 3, 1 ) \) so the \( 1 \le 1 \) predicate is true, resulting in a second call \( \textrm{isqrt_helper}( 4, 5, 1 ) \). For that call the \( 4 \le 1 \) predicate is false, resulting in a return value of \( 5 \).

  This time we have a final result of

  \begin{equation}\label{eqn:isqrt:40}
  \frac{5}{2} – 1 = 1,
  \end{equation}

  as desired again. The result will be the same for any value \( n \in [1,3] \).

• \( n = 4 \). We will end up with a call to \( \textrm{isqrt_helper}( 4, 5, 4 ) \) for which the \( 4 \le 4 \) predicate is true, resulting in a followup call of \( \textrm{isqrt_helper}( 9, 7, 4 ) \). For that call the \( 9 \le 4 \) predicate is false, resulting in a return value of \( 7 \).

  This time we have a final result of

  \begin{equation}\label{eqn:isqrt:45}
  \frac{7}{2} – 1 = 2,
  \end{equation}

  as expected. We get the same result for any value \( n \in [4,8] \).

Recurrence relations

The rough pattern of the magic involved can be seen. We have a sequence of calls

• \( \textrm{isqrt_helper}( 1, 3, n ) \),
• \( \textrm{isqrt_helper}( 4, 5, n ) \),
• \( \textrm{isqrt_helper}( 9, 7, n ) \),
• \( \textrm{isqrt_helper}( 16, 9, n ) \),

which terminates at the point where the first (square) parameter exceeds that value that we are taking the root of. Let the parameters of the sequence of calls be \( s_k \), and \( d_k \), so that with \( s_0 = 1, d_0 = 3 \) the \( k \in [0,…] \) call to the helper function is \( q_k = \textrm{isqrt_helper}( s_k, d_k, n ) \).

The sequence for the second parameter, the eventual return value, can be summarized compactly as \( d_k = 3 + 2 k \). It is not entirely obvious how we end up with a square for the values \( s_k = s_{k-1} + d_{k-1} \), but this follows by summation. For \( k > 1 \) that is

\begin{equation}\label{eqn:isqrt:60}
\begin{aligned}
s_k
&= s_{k-1} + d_{k-1} \\
&= s_0 + d_0 + d_1 + d_{k-1} \\
&= s_0 + \sum_{m=0}^{k-1} d_m \\
&= s_0 + \sum_{m=0}^{k-1} (3 + 2 m ) \\
&= s_0 + \sum_{m=1}^{k} (3 + 2 (m-1) ) \\
&= s_0 + \sum_{m=1}^{k} (1 + 2 m ) \\
&= 1 + k + 2 \sum_{m=1}^{k} m \\
&= 1 + k + 2 \frac{k(k+1)}{2} \\
&= k^2 + 2 k + 1 \\
&= (k+1)^2.
\end{aligned}
\end{equation}

This clearly holds for the boundary cases \( k = 0,1 \) as well. This allows the helper function action to be summarized more compactly

\begin{equation}\label{eqn:isqrt:80}
\textrm{isqrt_helper}(1, 3, n) = 3 + 2 k,
\end{equation}

where \( k \) is the smallest integer such that \( (k+1)^2 > n \). After integer scaling the final result is

\begin{equation}\label{eqn:isqrt:100}
(3 + 2 k)/2 -1 = k.
\end{equation}

This little beastie makes sense after deconstruction, but it was very Jackson like to toss this into the book without comment or explanation.

As pointed out by Pramod Gupta, there’s a spooky appearance of collaboration between Stroustrup and Jackson’s publishers, not entirely limited to the book covers.

References

[1] Bjarne Stroustrup. The C++ Programming Language, 4th Edition. Addison-Wesley, 2014.