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?
$\endgroup$ 74 Answers
$\begingroup$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 initially 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 one 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 iteration is a one-liner
while a^3>n do a:=(2*a+n/a^2)/3 odin 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 exercise (in other words I'm too lazy) to show this rigorously.
$\endgroup$ 1 $\begingroup$There is a "long division" type algorithm for cube root similar to that for square root. See But binary search is easier to implement and just as fast.
$\endgroup$ 3 $\begingroup$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 , (this is a bad site, im sure you could find better though)
$\endgroup$ $\begingroup$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.
$\endgroup$
