How to Compute √2 Efficiently: Binary Search, Newton’s Method, and C Tricks

Source: Algorithm interview question

Problem

During an interview, the candidate was asked how to compute the value of √2.

Approach

Two main methods are presented: binary search and Newton’s iteration. The article also mentions using the Taylor series and discusses how the standard library sqrt function is implemented, typically using a clever variant of Newton’s method for high efficiency.

Illustrations of the iterative process:

Code Implementation

Newton’s method (JavaScript)

function sqrt(n) {
    let res = n >= 1 ? n : 1;
    while (res * res - n > 1e-8) {
        res = 0.5 * (res + n / res);
    }
    return res;
}

C library function (source)

float invSqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int*)&x;
    i = 0x5f375a86 - (i >> 1);
    x = *(float*)&i;
    x = x * (1.5f - xhalf * x * x);
    x = x * (1.5f - xhalf * x * x);
    x = x * (1.5f - xhalf * x * x);
    return x;
}

Note: The C function returns the reciprocal of √x; the actual √x can be obtained by taking the inverse of the result.