[FIXED] Cube root in Python 3 using Bisection Search: Numbers in -1 to 0

Issue

Here is my code, which doesn't seem to work for numbers in between -1 and 0 (works perfectly fine otherwise)

I think the code enters an infinite loop, somehow, hence I get no result after entering the number. Please have a look and let me know what changes should be made. I am a beginner at programming and would appreciate any help!

    cube = float(input('Enter:'))
if abs(cube) > 1:
    num_guesses = 0
    epsilon = 0.0001
    low = 0
    high = cube
    guess = (high + low) / 2.0

    while abs(abs(guess) ** 3 - abs(cube)) >= epsilon:
        if cube > 0:
            if guess ** 3 < cube:
                low = guess
            else:
                high = guess
            guess = (low + high) / 2.0
            num_guesses += 1
        else:
            if guess ** 3 > cube:
                low = guess
            else:
                high = guess
            guess = (low + high) / 2.0
            num_guesses += 1

if abs(cube) < 1:
    num_guesses = 0
    epsilon = 0.0001
    low = cube
    high = 1
    guess = (high + low) / 2.0

    while abs(abs(guess) ** 3 - abs(cube)) >= epsilon:
        if cube > 0:
            if guess ** 3 < cube:
                low = guess
            else:
                high = guess
            guess = (low + high) / 2.0
            num_guesses += 1
        else:
            low = -1
            high = cube
            if guess ** 3 > cube:
                high = guess
            else:
                low = guess
            guess = (low + high) / 2.0
            num_guesses += 1


print(num_guesses)
print('The cube root of',cube,'is closest to',guess)

Thanks a lot!

Solution

Your code can be simplified by changing the condition to

abs(guess ** 3 - cube) >= epsilon

In fact, you have to use this condition instead of

abs(abs(guess) ** 3 - abs(cube)) >= epsilon

since the latter can give false positives (and thus exit the while-loop prematurely). For example, if guess equals 2 and cube equals -8, then the latter condition is True even though 2 is not the cube root of -8.

In [65]: guess, cube, epsilon = 2, -8, 0.0001

In [67]: abs(abs(guess) ** 3 - abs(cube)) >= epsilon
Out[67]: False  <-- would cause the while-loop to abort prematurely

In [68]: abs(guess ** 3 - cube) >= epsilon
Out[68]: True

---

Notice that in your code sometimes low can be bigger than high. For example, if cube < 0, then low and high are initialized this way:

if abs(cube) > 1:
    low = 0
    high = cube

Especially since we are bisecting, it would helpful if we could rely on low always being <= high. If we document and abide by a self-imposed coding contract that low <= high, and if in addition we choose low and high in such a way so that the cube root is always between low and high, then the code becomes much much simpler:

cube = float(input('Enter:'))

num_guesses = 0
epsilon = 0.0001

# Coding contract: low <= (cube root of cube) <= high
low = min(cube, -1)
high = max(cube, 1)

guess = (high + low) / 2.0

while abs(guess ** 3 - cube) >= epsilon:
    if guess ** 3 < cube:
        low = guess
    else:
        high = guess
    guess = (low + high) / 2.0
    num_guesses += 1

print('num_guesses = {}'.format(num_guesses))
print('The cube root of',cube,'is within epsilon of',guess)
print('{}**3 = {}'.format(guess,guess**3))

It is no longer necessary to handle cases for abs(cube) > 1, abs(cube) < 1, cube > 0 or cube <=0. All values of cube can be handled the same way, since guess**3 - cube is a monotonically increasing function of guess. If guess**3 > cube, guess is too large so decease guess. If guess**3 < cube, guess is too small so increase guess. The logic of how to adjust low and high become simple since we know low <= high.

---

By the way, in your original code, the

else:
    low = -1
    high = cube

in the final else clause is part of the reason why your code was falling into an infinite loop. The low and high should only be initialized once. Placing these lines inside the while loop resets low and high to a wide, naive interval, and throws away the work done by previous iterations of bisection.

Answered By - unutbu