One of the first topics that I wrote in this website was related to compile time computation in C++. Recently, I was reminded of it again when I was reading a book called Hacker’s Delight where there was a chapter on computing cube root of a number. As we have seen in a previous post, constexpr functions can be used for calculations to be performed in compile time. Last time, I used a recursive single line newton raphson based method to compute the square-root of a number. This was because I was writing code for C++11, where we could not have any loops or conditional statements in a constexpr function and it had to be a single line recursive implementation.

We can use a similar method to compute the cube root of a number, but then what’s the advantage of having a compiler supporting C++14 🙂 With C++14, you can have constexpr functions that can have loops and conditional statements that can be evaluated at compile time. The cube-root implementation using loops can be used with constexpr as shown below:

#include <iostream>
constexpr auto icbrt(unsigned x)
{
 unsigned y=0, b = 0;
 for (int s = 30; s >= 0; s = s - 3)
 {
    y = y<<1;
    b = (3*y*y + 3*y  + 1) << s;
    if (x >= b) 
    {
        x = x - b; y = y + 1; 
    } 
  }
  return y;
}

int main()
{
    auto cube_root = icbrt(125);
    std::cout<<cube_root<<std::endl;
}

This algorithm is taken from the book Hacker’s delight and works only with unsigned integers. The cube root for the number is computed during compile time as shown in the generated assembly, In the highlighted line you can see the pre-computed value 5 moved into a address location, without needing any additional function calls(You can have a look at the full assembly here):

main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        mov     DWORD PTR [rbp-4], 5
        mov     eax, DWORD PTR [rbp-4]

Note: You can achieve the same results using the standard function std::cbrt.