Sqrt(x)

May 12, 2022

I came across a fun exercise on LeetCode, where you have to calculate $f(x) = \sqrt{x}$, without using the standard library functions. Wikipedia has plenty of implementations to solve this problem efficiently, but I figured it would be a fun excercise to come up with a solution of my own.

Binary search algorithm

My approach was to determine an upper and a lower bound, and do a binary search to find the solution. Let $L$ be the lower bound. Since we know that a square root function requires that $x > 0$, we can set $L = 0$. Likewise, let $U$ be the upper bound. We know that $\sqrt x < x$ (if $x > 1$), which we use to define the upper bound $U = \max(1, x)$.

The guessing game

Now we are going to guess what $\sqrt x$ is. We know that $\sqrt{x}$ lies between $L < \sqrt x < U$. Let $k$ be our guess and initially set this to $k = \frac{L + U}{2}$.

Next we calculate the absolute error of our guess, which is $\left|\ \sqrt{x} - k\ \right| \leq \epsilon$. However, because of the challenge we cannot calculate square root functions. Therefore we are going to square it and compare $k^2$ with $x$, giving $\left|\ x - k^2\ \right| \leq \epsilon^2$. While the error is bigger than $\epsilon^2$, we need to adjust our guess. We do this by comparing $k^2$ to $x$ to determine which bound needs to be adjusted.

If $x < k^2$ then we adjust the upper bound to $U := k$.
If $x > k^2$ then we adjust the lower bound to $L := k$.

Once the bounds are updated, we recalculate our guess. The illustration below demonstrates the entire process by calculating $\sqrt 8$ as an example. The red circle is the guess $k$, and the black dot is the answer.

It starts by defining the upper and the lower bound to get to the first guess which is $4$. Comparing this to $k^2$ results in over-shooting, so the upper bound is adjusted and the next guess is $2$. Here it finds that it under-shoots so the lower bound is adjusted resulting in the next guess which is $3$. This process repeats until the absolute error is less than $\epsilon^2$.

This entire idea is the same as a well known game where you have to guess a number between $0$ and $100$. After every guess the player will learn if the guess was above the number or below the number. Based on that information, the player can adjust the guess. The binary search technique is a common strategy for solving this game efficiently.

Implementation in C#

The implementation of the algorithm can be found below. It has been implemented in C#. The time complexity of the algorithm is $O(\log x)$, because the search space is reduced by half on each iteration.

 1public int MySqrt(int x) {
 2    
 3    double lowerBound = 0;
 4    double upperBound = Math.Max(1, x);
 5    double guess = (upperBound + lowerBound) / 2;
 6    double epsilon = 0.1;
 7    double epsilonSquared = epsilon * epsilon;
 8    
 9    while (Math.Abs(guess * guess - x) > epsilonSquared 
10        || guess * guess < x) 
11    {
12        double guessSquared = guess * guess;
13        
14        if (x < guessSquared) {
15            upperBound = guess;
16        }
17        
18        if (x > guessSquared) {
19            lowerBound = guess;
20        }
21        
22        guess = (upperBound + lowerBound) / 2;
23    }
24    
25    return (int)guess;
26}

The check $\text{guess}^2 < x$ ensures that it is always over-estimating the guess. This is an important step to get the correct solution because the answer needs to be truncated.