switch to
==code(python) |

while abs(c - lo * lo * lo) < 1e-3:

while abs(c - lo * lo * lo) > 1e-3:

==
This doesn't work. For large numbers like 1e37 the code goes into an infinite loop. Try to figure out why. Discuss it in the comment section. Let’s try using the *relative error* (|(a - b) / b| < eps). There are some weird cases when a and b are close or equal to 0. Can the code be cleaner?

*Tomek Czajka(of topcoder fame) pointed out that my final version was buggy as well. I chose the number of iterations to be 120 but that’s way too small. It doesn't work for c = 1e60.*

A double is represented by the mantissa which consists of 52 bits and the exponent which contains 11 bits. One loop iteration either decreases the exponent of our interval by 1 or we find out a new bit of the mantissa. The maximum value of the exponent is 2^11^ and the mantissa has 52 bits. Thus we need 2100 steps to figure out the answer.

A double is represented by the mantissa which consists of 52 bits and the exponent which contains 11 bits(signed). One loop iteration either decreases the exponent of our interval by 1 or we find out a new bit of the mantissa. The maximum value of the exponent is 2^10^ and the mantissa has 52 bits. Thus we need about 1100 steps to figure out the answer.

==code(python) |
def _cubicRoot(c):
    lo, hi = 0.0, max(1, c)

    for iter in range(0, 2100):

    for iter in range(0, 1100):

        mid = lo + (hi - lo) / 2
        if (mid * mid * mid < c):
            lo = mid

notes:

* Thanks Tomek for the feedback.

* Thanks Tomek for pointing out the iteration problem and possible efficient solutions.
* When c is large, mid * mid * mid will overflow but the algorithm still works.

* We’ve addressed negative numbers, numbers in (0, 1), overflow problems, absolute and relative error problems.

* Instead of |(a - b) / b| < eps we can use |(a - b) / max(a, b)| < eps. Since a, b >=0 in our problem, we won’t get the nasty cases I was talking about previously, except for the c = 0 case.

* Some tests for your own code -1, 0, 1, 2, 8, 0.001, 1e30, 1e60
* In practice faster methods like Newton Rapson method are used.

public

protected