Showing that a cube root approximation has no decrementing function/loop variant

Question

I'm not sure if I've phrased the title correctly, but my question is about the following (Python) code that tries to approximate the cube root of some number x:

x = 10000
epsilon = 0.1
step = 0.01
ans = 0.0

while abs(ans**3 - x) >= epsilon:
    ans = ans + step
    print(ans)

Running this code for x = 10000 results in an infinite loop.

I understand that this happens because the step size is too big in this case (so it ends up skipping over the cube root of 10000). But it's troubling me that I would not have been able to foresee this just by looking at the code alone and I was wondering if there was a way to show that this loop does not terminate for all values of x?

I'm also not sure how the author would have known to try x = 10000 - how can I find other values that cause the loop to fail?

Answer 1

You are trying out, successively, numbers of the form $a=k·h$. The gap between the cubes of two neighboring elements of this sequence is $$(a+h)^3-a^3=h·(3a^2+3ah+h^2).$$ The cubes, plusminus the tolerance $\epsilon$, form a "net" in which you aim to catch the input number $x$. For that to work, the net should have no gaps around $x$. So you need $$ a^3+ϵ > (a+h)^3-ϵ\iff h<\fracϵ{3a^2+3ah+h^2}. $$ Now we do not know what $a$ is, as that is the output to be computed. One can insert an upper bound for $a$ and $h<1$ into the right side, or use that as $x>27$ then $a>3$ to establish the stricter condition $h\le \fracϵ{x}$.

---

Of course, this gives unrealistic step sizes. So just use the monotonicity and iterate while a**3 < x: to find the interval that contains the cube root.

---

To be faster, start with a geometric progression

a=b=1
while b<x: a*=2; b*=8

and then continue the search inside the interval $[a/2,a]$.

Using pure "function table lookup", for monotonous functions the bisection method is still the fastest.

Using the smoothness of the cube function, using secant roots or tangent roots as midpoints in an intelligent way will again increase the speed of convergence.

A very fast convergence is obtained from applying Newton's method to $f(a)=a^2-x/a$