Now that we have covered the basics of Python in our Pythonic Way Series, it is time to start thinking about how we can combine those learnings to write some simple programs.

Exhaustive Enumeration

The following code prints the integer cube root, if it exists, of an integer. If the input is not a perfect cube, it prints a message to that effect.

#Find the cube root of a perfect cube
x = int(input("Enter an integer: "))
ans = 0
while ans**3 < abs(x):
    ans = ans + 1
if ans**3 != abs(x):
    print(x, "is not a perfect cube")
else:
    if x<0:
        ans = -ans
    print("Cube root of", x, "is", ans)

In Python, the abs(x) function is used to return the absolute value of a number x

So now for what values of x will this program terminate? The answer is,"all integers." How ?

• The value of the expression ans**3 starts at 0, and gets larger each time through the loop.

• When it reaches or exceeds abs(x), the loop terminates.

• Since abs(x) is always positive there are only a finite number of iterations before the loop terminates.

Whenever you should write a loop, you should think about an appropriate decrementing function. This is a function that has the following properties:

1. It will map some set of program variables to an integer.

2. The value of the variable is non-negative when entering the loop for first time.

3. When the value of the integer is less than 0, loop terminates.

4. The value is decreased each time in the loop.

These 4 property guarantees to terminate the loop, Also there is a possibility to count up to a value, but we can always use some logic to always decrement in place of increment.

So how do we find the decrementing function of the above code?

As per the first property we have to find a program variable which can store integers, and we have only 2 program variables in the code, x and ans.

The decrementing function will be,

abs(x) - ans**3

Considering x=9 to start with the steps will be as shown below

So when the ans becomes 3, the loop exits.

Now a lot of you might be thinking where is this abs(x) - ans**3 in the actual code mentioned above, it is explicitly not present, so if you look in the code, we are actually doing this step, in a multiple ways.

We are incrementing the ans variable each time in the while loop. And the whilecondition test the condition ans*ans*ans < abs(x) which can rather be modified to abs(x) - ans**3 as both means the same.

The above code uses the method called Guess and Check, where we are basically Guessing a answer and then checking. This is also called Exhaustive Enumeration.

The reason it is called Exhaustive Enumeration, because we go through the complete answer set and then decide if we have achieved the answer. So by this we mean we are exhausting the answer space. The Exhaustive Enumeration Technique is also called Brute Force technique

Approximation and Bisection Search

An approximation is anything that is intentionally similar but not exactly equal to something else. -Wikipedia

A lot of programs can’t guarantee exact answer, but can just look for something close enough i.e, approximation

• I have to define what's a close enough solution

• start with a guess and increment by some small value

• define a constant (Epsilon) which is going to be something that tells me how close I want to get to the answer.

decreasing increment size ———> slower program increasing epsilon —————> less accurate answer

---

One such example of approximation is finding cube root

• guess here is the close enough solution

• epsilon is the constant that will define how precise the solution should be

• increment will be use to increment the value of guess unless and until guess is close enough to the solution

cube = int(input())
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0
while abs(guess**3 - cube) >= epsilon and guess <= cube :
    guess += increment
    num_guesses += 1 
print('num_guesses =', num_guesses) 
if abs(guess**3 - cube) >= epsilon:
    print('Failed on cube root of', cube) else:
print(guess, 'is close to the cube root of', cube)

Few Problems with approximation:

Step(incrementation) could be any small number

◦ If too small, takes a long time to find cube root

◦ If too large, might skip over answer without getting close enough

Bisection search is the process used to guess a value for a solution, check whether that value is too high or too low to be correct, eliminate all other values that may be too high or too low as well, and keep guessing from the remaining values until a solution is found or all.

Here is an example of finding cube root using bisection search

Here in while loop code block we can see narrowing down the search space based on wether the guess is too high or too low to be correct.

cube = int(input())
epsilon = 0.01
num_guesses = 0
low = 1
high = cube
guess = (high + low)/2.0
while abs(guess**3 - cube) >= epsilon:
    if guess**3 < cube :
        low = guess
    else:
        high = guess
    guess = (high + low)/2.0
        num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to the cube root of', cube)

Advantage of bisection search is that it takes way lesser computation time than approximation and also more accurate since we are narrowing down the search space with every iteration.