Your solution has two problems with using floating point arithmetic. The first problem is that the Python float contains only 16 significant decimal digits of precision, so as soon as your answer requires more than 16 significant digits or so (so there are more than 6 digits before the dot and 10 digits after), you "We are very small hope to get the correct lagging numbers. The second problem is more subtle and affects even small n values. That your approach of rounding to 11 decimal digits and then dropping the last digit suffers from potential errors due to double rounding . For example, take n = 33 Cube root n , up to 20 decimal places or so:
3.20753432999582648755...
When it is rounded to 11 places after the point, you will get
3.20753433000
and now dropping the last digit gives 3.2075343300 , which you did not want. The problem is that rounds up to 11 decimal places can ultimately affect the numbers to the left of the 11th place number.
So what can you do to fix this? Well, you can generally avoid floating point and reduce this to a pure integer problem. We need the cube root of the integer n to ten decimal places (rounding the last place down). This is equivalent to calculating the root of the cube 10**30 * n nearest integer, rounding down again, and then dividing the result by 10**10 . Thus, the main task here is to calculate the floor of the cubic root of any given integer n . I was not able to find any existing answers about stack overflow about calculating the roots of integer cubes (even less in Python), so I thought it was worth showing how to do this in detail.
Calculating the cubic roots of integers turns out to be quite simple (using the tiny part of mathematics). There are various possible approaches, but one approach that is efficient and easy to implement is to use a clean whole version of the Newton-Raphson method . For real numbers, Newton's method for solving the equation x**3 = n takes an approximation x to the cube root of n and iterations return an improved approximation. Required Iteration:
x_next = (2*x + n/x**2)/3
In the real case, you should repeat the iteration until you reach any desired tolerance. It turns out that essentially the same iteration takes place over integers, and with the correct exit condition, this will give us exactly the right answer (without tolerance). Iteration in the integer case:
a_next = (2*a + n
(Note the use of the // division operator // instead of the usual real division operator / above.) Mathematically, a_next is exactly the floor (2*a + n/a**2)/3 .
Here is some code based on this iteration:
def icbrt_v1(n, initial_guess=None): """ Given a positive integer n, find the floor of the cube root of n. Args: n : positive integer initial_guess : positive integer, optional. If given, this is an initial guess for the floor of the cube root. It must be greater than or equal to floor(cube_root(n)). Returns: The floor of the cube root of n, as an integer. """ a = initial_guess if initial_guess is not None else n while True: d = n//a**2 if a <= d: return a a = (2*a + d)//3
And in some example used:
>>> icbrt_v1(100) 4 >>> icbrt_v1(1000000000) 1000 >>> large_int = 31415926535897932384626433 >>> icbrt_v1(large_int**3) 31415926535897932384626433 >>> icbrt_v1(large_int**3-1) 31415926535897932384626432
There are several troubles and inefficiencies in icbrt_v1 that we will fix in the near future. But first, a brief explanation of why this code works. Note that we start with the initial assumption, which is assumed to be greater than or equal to the floor of the cube. We show that this property is a loop invariant: every time we reach the top of the while loop, a at least floor(cbrt(n)) . In addition, each iteration gives a value strictly less than the old one, so our iteration ultimately converges to floor(cbrt(n)) . To prove these facts, we note that when entering a while , two possibilities are possible:
Case 1. a strictly greater than the cubic root of n . Then a > n//a**2 , and the code proceeds to the next iteration. Write a_next = (2*a + n//a**2)//3 , then we have:
a_next >= floor(cbrt(n)) . This follows from the fact that (2*a + n/a**2)/3 is at least the cubic root of n , which, in turn, follows from the AM-GM inequality applied to a , a and n/a**2 : the geometric mean of these three quantities exactly matches the cubic root of n , so the arithmetic mean must be at least the cubic root of n . Therefore, our invariant cycle is preserved for the next iteration.
a_next < a : since we assume that a greater than the root of the cube, n/a**2 < a , and it follows that (2a + n/a**2) / 3 less than a , and, therefore, floor((2a + n/a**2) / 3) < a . This ensures that we move forward to the solution at each iteration.
Case 2. a less than or equal to the cubic root of n . Then a <= floor(cbrt(n)) , but from the above invariant of the cycle we also know that a >= floor(cbrt(n)) . So, we are done: a is the value we need. And the while loop exits from this point, since a <= n // a**2 .
There are several problems with the code above. First, starting with the initial guess, n inefficient: the code will spend the first few iterations (approximately), dividing the current value of a by 3 each time until it falls into the neighborhood of the solution. The best choice for the initial assumption (and easily computable in Python) is to use the first degree of two, which exceeds the root of the cube n .
initial_guess = 1 << -(-n.bit_length() // 3)
Even better, if n is small enough to avoid overflow, you should use floating point arithmetic to provide an initial assumption, with something like:
initial_guess = int(round(n ** (1/3.)))
But this leads us to our second problem: the correctness of our algorithm requires that the initial assumption be no less than the actual integer cubic root, and with increasing n we cannot guarantee that for float-based initial_guess higher (although for sufficiently small n we can) . Fortunately, there is a very simple fix: for any positive integer a , if we perform one iteration, we always get a value that is at least floor(cbrt(a)) (using the same AM-GM argument that we used above). So, all we need to do is complete at least one iteration before we start convergence testing.
With this in mind, a more efficient version of the above code is here:
def icbrt(n): """ Given a positive integer n, find the floor of the cube root of n. Args: n : positive integer Returns: The floor of the cube root of n, as an integer. """ if n.bit_length() < 1024:
And with icbrt in hand, it's easy to put together everything to calculate the roots of a cube of up to ten decimal places. Here, for simplicity, I output the result as a string, but you can just as easily build an instance of Decimal .
def cbrt_to_ten_places(n): """ Compute the cube root of `n`, truncated to ten decimal places. Returns the answer as a string. """ a = icbrt(n * 10**30) q, r = divmod(a, 10**10) return "{}.{:010d}".format(q, r)
Output Example:
>>> cbrt_to_ten_places(2) '1.2599210498' >>> cbrt_to_ten_places(8) '2.0000000000' >>> cbrt_to_ten_places(31415926535897932384626433) '315536756.9301821867' >>> cbrt_to_ten_places(31415926535897932384626433**3) '31415926535897932384626433.0000000000'