Find Cube root using Binary Search

In this article, we have explained the algorithm to Find Cube root using Binary Search along with Time and Space Complexity analysis.

Table of contents:

1. Introduction
2. Finding cube root using Binary Search
   • Perfect Cube
   • Cube root with precision
3. Time and Space Complexity

Pre-requisites:

• Binary Search
• Find Square root using Binary Search

Introduction

When someone needs to find the cube of a number, then they can just multiply that number by itself three times, and alas! They have the answer. But, when one needs to go in the other direction (finding cube-root), theirs no direct formula to find this number and, because of this it is required to search this number throughout the space of [1, N].

A little stroll to Linear Search

If you desire, you can skip this and goto the solution

So, I was curious, why not Linear Search? I mean, it's ∛N. maybe a mathematician would know by one look which one is smaller or greater ∛N or log2N.

Well in my case, I went and took the log of a bunch of numbers and then compared them together and got the following output.

from math import ceil, log
for i in range(1, 30, 2):
    print("{} - {} | {} - {}".format(
             i,
            ceil(log(i**3, 2)),
            i+1,
            ceil(log((i+1)**3, 2))
        )
    )

         1  -  0      |      2  -  3
         3  -  5      |      4  -  6
         5  -  7      |      6  -  8
         7  -  9      |      8  -  9
         9  -  10     |     10  -  10
        11  -  11     |     12  -  11
        13  -  12     |     14  -  12
        15  -  12     |     16  -  12
        17  -  13     |     18  -  13
        19  -  13     |     20  -  13
        21  -  14     |     22  -  14
        23  -  14     |     24  -  14
        25  -  14     |     26  -  15
        27  -  15     |     28  -  15
        29  -  15     |     30  -  15

Conclusion:

As you go further, log starts to become smaller, therefore, log2N < ∛N. So, binary search would be better than Linear.

Well, back to the topic...

Finding cube root using Binary Search

Perfect Cube

If we have to find cube root for a perfect cube, then we can just apply binary search directly on the space of [1, N], and return x where x equals to x3.

This should look something like the following,

1  def perfect_cube_root(N):
2     start = 1
3     end = N
4     mid = (start + end) // 2
5    
6     while mid != start and mid**3 != N:
7         if mid**3 > N:
8             end = mid
9         else:
10            start = mid
11        mid = (start + end) // 2
12    return mid

The (mid != start) and condition, in the while loop, help to return a smaller value in case the loop doesn't find a perfect cube root. And without this condition, the loop will run infinitely.

So, for example,

If we do perfect_cube_root(9), since 9 comes between two perfect cubes 8 and 27 because of this, the above loop will return 2, which is a cube-root of 8.
Why write this function this way?

Well, we're going to use this in the next cube_root with precision function.

Cube root with precision

Now to find decimal values of a cube root, we can first search for a smaller result using perfect_cube_root(N) and, if it returns a perfect cube root, then return it or proceed to search for precision.

The idea here is to find a value in decimal which will be a perfect cube root or a nearest smaller value.

In other words, we will search between .0 and .9, a perfect match or nearest smaller value, and then decrease the power in the case of .0 and .9, another search will happen in-between .00 and .09.

And while the above search happens, we should keep adding the found values to the result with increasing precision.

Code for the above idea should look like the following one:

1  def cube_root(N, precision=5):
2     P = lambda a, b: a * 10 ** (-b)
3     result = perfect_cube_root(N)
4     if result**3 == N:
5         return result
6 
7     for i in range(1, precision + 1):
8         start = 0
9         end = 9
10        mid = (start + end) // 2
11
12        cube = lambda: (result + P(mid, i))**3
13
14        while start != mid:
15            if cube() > N:
16                end = mid
17            elif cube() < N:
18                start = mid
19            elif cube() == N:
20                return result + P(mid, i)
21
22            mid = (start + end) // 2
23
24        result += P(mid, i)
25
26    return round(result, precision)

Let us look at an example,
If we run cube_root(16.003008) then it should return 2.52.

At first, the cube_root will call perfect_cube_root, and surely it will get the 2 in return.

Now at line 7 we start for-loop for a range of [1, precision + 1] and initialize start, end and mid as 0, 9 and 4.

Notice, start, end, and mid are not decimals reason for that is just that I did not want to deal with float numbers. Calculating mid with float values was a mess and, this approach makes it easier to capture a smaller value if it did not find any value, to form a result for perfect cube root.

Anyway, since i = 1 therefore here we're dealing with 10-1 precision, means we're searching for perfect or small in between 2.0 and 2.9, at this point when loop will take start and mid at 5, start != mid will break the loop and will proceed for 10-2.

Hence, it will start searching between 2.50 and 2.59, in this the loop will find 2.52 as a perfect match and, line 20 will execute, which will add 0.02 ( P(mid, i) ) to result and return it.

Time and Space Complexity

Time Complexity:

At first, we're performing purely a binary search which should take O(logN) time,

then after this, we perform binary search on space of [0, 9], for P times,
which will total to, Plog(10)
that is, 4P.
therefore,

Time Complexity = O(logN + P)

Space Complexity:

The function itself takes one Number and creates a constant number of variables which use a constant number of space,
therefore,

• Space Complexity = O(1)

With this article at OpenGenus, you must have the complete idea of Finding cube root using Binary Search.