When working with microcontrollers, floating point number computation are often not available in hardware. Modern toolchains normally provide a math library having a software simulation for floating point and math functions: this is time consuming and may even be useless, because microcontrollers do normally work with integer numbers (e.g. the input of an ADC).

Nevertheless, some advanced math functions are quite often needed. One of them is the square root. The Newton-Raphson method is probably the simplest and most powerful method for obtaining it. Going straight to the point, this is the C code you may find useful:

newton_sqrt.c (Source)

#define X_INIT (1 << 8) /* Arbitrary initial value for x */
unsigned long newton_sqrt(unsigned long z)
{
        unsigned long x;
        unsigned long x_next = X_INIT;
        int maxiter = 8 * sizeof(z);

        while (x != x_next  && maxiter-- > 0) {
                x = x_next;
                x_next = (x + z / x) / 2;
        }
        return x;
}

Here follows some math explaining it.

Said \(z\) the number you want to find the square root of, the problem is equivalent to finding the solution of the equation: \(x ^ 2 - z = 0\)

In other words, said \(y(x) = x ^ 2 - z\), we are looking for the zeros of \(y(x)\). This can be achieved by using the Newton-Raphson method, with, for our \(y(x)\), converges for any \(z\) >= 0. Leaving out any demonstration, the iterative formula is:

Since \(f'(x_{k}) = 2x_{k}\), we get:

Looking back to the above C function, x variable is \(x_{k}\), x_next is \(x_{k+1}\), and the loop is repeated up to the number of bits of our integer number.

The only parameter to be tuned is X_INIT value: it should be chosen the closest to the typical results we are expecting.

I will follow up with another article analyzing the performance, accuracy and possible improvements for the newton_sqrt function.