Implementing sqrt

Ale

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:

\sqrt{n} = x

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

n = x^2

Move to the left of the equality:

0 = x^2 - n

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:

x_{n+1} = x_n - \frac{f(x)}{f'(x)}

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).

f'(x) = \frac{f(x+h) - f(x)}{h}

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

|x_{n+1} - x_n|

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