# Finding the cube root of a number using integer arithmetic only?

Is it possible to find cube root of a 150-200 digit decimal number correct truncated (not rounded ) upto 10 decimal places using integer arithmetic only? The question is an algorithmic one not a pure maths one. What method can be used here?

Can Newton method be modified with both estimates x1 and x2 to be integers? Also can a binary search be utilized for searching the cube root with its search area having decmals upto 10 places?

-
– Zev Chonoles Dec 21 '12 at 7:11
Actually as I said,I need this answer for algorithmic purposes.This is the actual problem statement.spoj.com/problems/CUBERT – user1907531 Dec 21 '12 at 7:17
I agree, I was only joking :) – Zev Chonoles Dec 21 '12 at 7:23
Do you want $10$ decimal places in the original number or in the answer, or both? – Robert Israel Dec 21 '12 at 7:36
Without using conditional statements (that is as a single formula) no, because the output would be always rational. On the other hand, if you can change what you calculate depending on the input, of course it is, you can do it even with only logical operations like $\land$, $\lor$ and $\neg$, computers do it this way, don't they? Finally, places like SPOJ also test your thinking skills, not only coding, so try working out the solution yourself (and if you did and failed, you could let us know what have you tried)! – dtldarek Dec 21 '12 at 7:49

## 4 Answers

There is a "long division" type algorithm for cube root similar to that for square root. See http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm But binary search is easier to implement and just as fast.

-
:How can binary search e implemented on numbers till 10 places of decimal? – user1907531 Dec 21 '12 at 7:26
Multiply by an appropriate power of $10$ so you can use integer arithmetic. – Robert Israel Dec 21 '12 at 7:34
@user1907531 $\sqrt[3]{\frac{p}{q^{3n}}} = \frac{\sqrt[3]{p}}{q^n}$. – dtldarek Dec 21 '12 at 7:52

It depends on that nature of the number, I know for example if you have an integer you know for a fact is a perfect cube, you can take advantage of some facts about modular arithmetic to find the original root, I don't understand the second part of your question though. If your curious about my first statement here is a link http://calculus-geometry.hubpages.com/hub/Mental-Math-Trick-Find-the-Cube-Root-of-a-Perfect-Cube, (this is a bad site, im sure you could find better though)

-

Yes, there is an obvious procedure that will find the floor of the cube root of a positive integer $n$ rapidly and certainly. One maintains an approximation $a_i$ that is certain to be greater than the true cube root $\sqrt[3]n$. One could intially take $a_0=n$, but somewhat more sophisticated approximations will do a lot better; for instance the first power of $2$ to exceed $\sqrt[3]n$ is easy to give immediately if once has access to the number of binary digits of $n$, and fairly quickly found even if one doesn't. Now compute $$a_{i+1}=\left\lfloor\frac{2a_i+\lfloor n/a_i^2\rfloor}3\right\rfloor =\left\lfloor\frac{2a_i+ n/a_i^2}3\right\rfloor$$ (the first expression shows it only involves integer division, but the one on the right is easier for reasoning, and both are easily seen to be equal). Now $a_{i+1}^3\leq n$ then $a_{i+1}$ is the required answer (because the arithmetic mean of $(a_i,a_i,n/a_i^2)$ is greater than their geometric mean $\sqrt[3]n$, so the inequality can only hold due to application of the floor function), and otherwise $\sqrt[3]n<a_{i+1}<a_i$ ensures that we have improved our estimate, so we can iterate. The actual interation is a one-liner

while a^3>n do a:=(2*a+n/a^2)/3 od


in any programming language that has arbitrary-length integers.

In fact the convergence becomes considerably better than binary search as $a_i$ approaches $\sqrt[3]n$. Experimentation with numbers of more than $100$ digits shows that once one has got an approximation that is no more than twice as large as $\sqrt[3]n$ (as the power-of-two initialisation would provide), then every next approximation has about twice as many digits correct as the previous one. It would be an instructive exercice (in other words I'm too lazy) to show this rigourously.

-
Marc, I like this approach. By the way, arbitrary-length integers are not needed if the a^3>n and n/a^2 subexpressions are rewritten. For example, in C, the loop can be written as: while (a>n/a/a) a=(2*a+n/a/a)/3; to avoid overflow of fixed-length integers. – Todd Lehman Feb 27 '15 at 22:47

If you want the cube root of $x$ with exactly $n$ correct decimal digits (truncated, not rounded!) after the decimal place, then calculate the floor of the cube root of $10^{3n} x$ (an integer) and then divide it by $10^{n}$. Using binary search is certainly a valid and simple way to calculate $\lfloor \sqrt[3]{x} \rfloor$; it takes a linear number of steps in the length of $x$. Naively assuming that the individual steps take quadratic time in the length of $x$ gives an overall time $O(\log^{3} x)$, which is probably fast enough for your purpose.

-