I was reading some post about interview questions of 2011 and came across one that stated “find the square root of a number”.

Assuming we can’t use the sqrtf function of the standard C math library, let’s see how we can calculate the square root of a number **x**.

Given **n**, we know that its square root is a number **x** that holds:

Let’s work on this equation a little. Raise both sides to the second power:

Move to the left of the equality:

If we found the roots of this last equation somehow, we would have found the square root of **n**. We can do this by using the Newton-Raphson iteration.

The Newton-Raphson iteration states that we can find the root of an equation using the following formula iteratively:

Where **f'(x)** is the derivative of function **f(x)**. We will approximate the derivative using the definition of derivative at a point (we could also note that the derivative could be trivially calculated; this method is more general).

The error of the Newton-Raphson iteration is given by:

Starting with a hardcoded seed value, we will perform this iteration in a loop until the error is less than a given value. I have chosen to iterate until the error is less than 1×10^(-10): 0.00000000001.

Let us see what a tentative “pythonesque” pseudocode for this loop could be:

def sqrt(n):
f = function(x*x - n)
x = 1 # seed
xant = 0
do:
f1 = (f.eval(x+h) - f.eval(x)) / h
xant = x
x = x - f.eval(x)/f1
while abs(x - xant) > err;
return x

Assuming we have a symbolic function type, that loop does not seem too difficult. In order to code this in C, since the equation is always the same, I will hardcode it as a plain function.

typedef double real; // change to float for single precision
real f(real x, real n)
{
return x*x - n;
}
real sqrt(real n)
{
real err = 0.00000000001f;
real h = 0.01f;
real x = 1.0f; // seed
real xant = 0.0f;
do
{
xant = x;
real df = (f(x+h, n) - f(x, n))/h;
x = x - f(x, n)/df;
}
while (abs(x - xant) > err);
return x;
}

Here are the results of running our custom square root function, compared to the standard version provided with the C programming language:

[ale@syaoran sqrt]$ ./sqrt 1.0
Custom sqrt of: 1 = 1
libm sqrt of: 1 = 1
[ale@syaoran sqrt]$ ./sqrt 2.0
Custom sqrt of: 2 = 1.41421
libm sqrt of: 2 = 1.41421
[ale@syaoran sqrt]$ ./sqrt 4.0
Custom sqrt of: 4 = 2
libm sqrt of: 4 = 2
[ale@syaoran sqrt]$ ./sqrt 16.0
Custom sqrt of: 16 = 4
libm sqrt of: 16 = 4
[ale@syaoran sqrt]$ ./sqrt 32.0
Custom sqrt of: 32 = 5.65685
libm sqrt of: 32 = 5.65685
[ale@syaoran sqrt]$ ./sqrt 100.0
Custom sqrt of: 100 = 10
libm sqrt of: 100 = 10
[ale@syaoran sqrt]$ ./sqrt 1000000.0
Custom sqrt of: 1e+06 = 1000
libm sqrt of: 1e+06 = 1000