6
$\begingroup$

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?

  • 0
    I have submitted another solution in Python with a binary search solution,but I am getting wrong answer.2012-12-21

4 Answers 4

3

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.

  • 0
    @user1907531 $\sqrt[3]{\frac{p}{q^{3n}}} = \frac{\sqrt[3]{p}}{q^n}$.2012-12-21
3

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 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 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 exercise (in other words I'm too lazy) to show this rigorously.

  • 0
    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.2015-02-27
1

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)

0

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.