Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Indian claims finding new cube root formula

It has eluded experts for centuries, but now an Indian, following in the footsteps of Aryabhatt, one of the earliest Indian mathematicians, claims to have worked out a simple formula to find any number's cube root.

Nirbhay Singh Nahar, a retired chemical engineer and an amateur mathematician, claims he has found a formula that will help students and applied engineers to work out the cube roots of any number in a short time.

"Give me any number - even, odd, decimals, a fraction...and I will give you the cube root using a simple calculator to just add and subtract within a minute and a half. We do have methods and patterns, but no formula at the moment. Even the tables give cube roots of 1 to 1,000, not of fractions or of numbers beyond 1,000, for which people have to use scientific calculators," Nahar, who retired as an engineer from Hindustan Salts Ltd at Sambhar (Rajasthan), said.

Is there any sense to this claim? Is it possible to have an algorithm that gives the cube root which uses only additions and subtractions?

share|improve this question
13  
"I will not disclose the formula till it is patented because I want the credit for my work to go to India." It's hard to talk about math that you can't see. –  Dylan Moreland Feb 25 '12 at 1:02
25  
"Writing to Prime Minister to arrange meeting with world's top mathematicians" (for a cube root calculation shortcut!). In footsteps of Aryabhat. Hmm... I am thinking of changing my name till this question is deleted :-) –  Aryabhata Feb 25 '12 at 1:37
15  
I'm voting to reopen. OP's actual question "Is it possible to have an algorithm that gives the cube root which uses only additions and subtractions?" is perfectly valid without knowing the details of Nahar's claimed algorithm. –  Austin Mohr Feb 25 '12 at 2:15
17  
In Mathematical Cranks, Underwood Dudley describes a number of amateur mathematicians making comparable claims. They usually turn out to be methods for iteratively computing successive rational approximations to the desired cube root (or whatever). Even though the authors are wont to describe their work as solving age-old impenetrable riddles, such methods are completely without practical use since computers and inexpensive calculators can already compute cube roots for us. Often the methods are not even new, the authors just having rediscovered something that was known already. –  Henning Makholm Feb 25 '12 at 3:38
7  
If one wants to merely get better and better approximations of cube roots, then as readers of Surely You're Joking, Mr Feynman! may recall, this can be done on an abacus... –  user16299 Feb 25 '12 at 9:00

4 Answers 4

up vote 24 down vote accepted

If by "formula", Nirbhay (the former engineer featured in the article) means "closed form formula", then the answer is obviously not; because the answers would all have to be rational, whereas e.g the cube root of 2 is not. However, if by "formula" Nirbhay means "algorithm which computes the digits in sequence, which converges on the answer and terminates in the case of integers and other terminating fractions which are perfect cubes", then the answer is yes, if you allow either simple multiplications, or perform it in base 2. (Of course, you can reduce multiplication to addition if you like, but beyond small integers or shifting numbers by place values, that feels like cheating.)

No innovation is required; it's a simple modification of the digit-by-digit algorithm for computing square roots. The intuition behind this algorithm is that at each point, you are trying to get better and better approximations to X by constructing rational numbers Y1, Y2, Y3, ... having more and more digits, whose cubes approximate X from below. We chip away at the error between X and the cubes of these approximations by trying to "complete the cube". Each new digit of X that we consider allows us to try to chip away more of the difference between Y³ and X, by defining Yj+1 = Yj + δ for a suitable increment δ; we then determine the error involved in the new approximation by computing Yj+1³ = Y³ + 3δY² + 3δ²Y + δ³. The trick is how to do this with simple arithmetic operations; but it's not too difficult.

I demonstrate the algorithm in binary, because that's the base where it would be easiest in practise to compute the cube roots. The generalization to arbitrary bases (e.g. decimal) is an exercise for the reader. To simplify the presentation, we may assume without loss of generality that the number X whose cube-root we compute is less than 8. We may repeatedly divide by 8 until this is the case; when we have obtained the square root, simply multiply the answer the same number of times by 2. This is just observing that $\sqrt[3]{8^{-n} \cdot X\;} = 2^{-n} \cdot \sqrt[3]{X\;}$, and allows me to emphasize that the algorithm works just as well for fractions as for integers. Because of how the algorithm works, it looks somewhat as though it's starting with a number in octal, and obtaining a root in binary (for square roots it looks like it produces a binary root from a number in quartal); but of course we can represent the base 8 "digits" by groups of three binary digits.

Let X = x0 + x1/81 + x2/82 + ... , where each xj ranges from 0 to 7. We compute binary digits yj representing Y = y0 + y1/21 + y2/22 + ...  such that Y3 = X, as follows.

  • If x0 = 0, set y0 = 0; otherwise, set y0 = 1. Let R := x0 − y0.

  • Set A = B = Cy0 .

  • Set j = 1, and repeat the following until the desired number of digits is obtained (or until R = 0 and only if all the remaining digits xj , xj+1 , ... are also zero):

    1. Set D = 8R + xj , and consider the largest binary digit yj such that $$ D \;\;\geqslant\;\; y_j^3 + 6Ay_j^2 + 12By_j + 8C.$$ Of course, we're working with binary digits; all the powers of yj are either zero or one. So what we're really testing is whether or not $$ D \;\;\geqslant\;\; 1 + 2A + 4A + 4B + 8B + 8C,$$ where multiplication by 2, 4, and 8 can be realized by shifting integers one, two, or three places (tacking on zeros). If the inequality above holds, set yj = 1; otherwise set yj = 0.

    2. The integer A will actually be the number whose binary representation is the bit-sequence y0y1 ... yj−1 in order; B is equal to A², and C is equal to A³. To maintain this invariant for the next iteration j, we compute new values A', B', and C' as updated values. For A, we define $$ A' = 2A + y_j \;. $$ For B', we take advantage of the fact that we have B and A: $$\begin{align*} B' &= (A')^2 = (2A + y_j)^2 = 4A^2 + 4Ay_j + y_j^2 \\&= 4B + 4Ay_j + y_j^2 \;. \end{align*}$$ Similarly, for C': $$\begin{align*} C' &= (A')^3 = (2A + y_j)^2 = 8A^3 + 12A^2y_j + 6Ay_j^2 + y_j^3 \\&= 8C + 8By_j + 4By_j + 4Ay_j^2 + 2Ay_j^2 + y_j^3 \;. \end{align*}$$ Again, multiplications by zero, one, or powers of two are trivial inbinary representation. We then update A := A', B := B', and C := C'.

    3. We update R, which is meant to represent the error of C as an approximation to the integer formed by the first j digits (in octal) of X: we set $$ R' = \bigl(8R + x_j\bigr) - C' = D - C' \;,$$ and then set R := R'.

  • If ever we obtain R = 0 and with all of the remaining digits of X equal to zero, we stop (with an exact solution).

In fact, it is not very difficult to modify this algorithm to obtain a procedure for extracting fourth roots, fifth roots, or nth roots for any constant n (though the number of parameters you have to carry around with you, and the sizes of the additions you have to carry out, will grow as you work harder and harder to avoid explicitly performing any multiplications).

share|improve this answer
2  
Bravo, but somehow I doubt this is what Mr Nahar has in mind. –  Gerry Myerson Feb 26 '12 at 3:43
12  
Quite possibly he has in mind something much more suitably mysterious, using extremely clever ideas from ancient Indian mathematical tradition. I doubt that we shall ever learn what his algorithm is, so we must be content with the half-dozen known fast algorithms for computing cube roots. –  Niel de Beaudrap Feb 26 '12 at 10:22
    
Indeed, I used this same algorithm to compute cube roots for QuickDraw GX. –  robjohn Apr 17 '12 at 19:33

Is it possible to have an algorithm that gives the cube root which uses only additions and subtractions? Yes, if binary shifts are allowed. The algorithm is described in Henry S. Warren's "Hacker's Delight" (11-2 Integer Cube Root), also on line: icbrt2.

share|improve this answer

Unless there is something lost in translation, the claims in the article are inconsistent...

Even the tables give cube roots of 1 to 1,000, not of fractions or of numbers beyond 1,000, for which people have to use scientific calculators," Nahar, said.

While Newton's formula arrives at an approximation, Nahar claims his formula leads to direct and perfect value, and no approximation.

So, he claims to be able to do this for any number, including fractions, and get the perfect value, not an approximation.... Great, so he is able to calculate all the digits of $\sqrt[3]{2}$....

Judging by this, I have big doubts.

Of course it matters what he means by a formula; technically a formula of the type $x=10^{\frac{\log_{10} x}{3}}$ is simple enough and easy to use if one uses a logarithmic scale for the real numbers...

share|improve this answer

To put things in context I'll first expose a straightforward method inspired by the classical evaluation of square roots (shortly : "if we know that $a^2 \le N <(a+1)^2$ then the next digit $d$ will have to verify $(10a+d)^2 \le 10^2 N <(10a+d+1)^2$. This means that we want the largest digit $d$ such that $(20a+d)d\le 10^2(N-a^2)$") :

To evaluate the cubic root of $N$ let's suppose that $a^3 \le N <(a+1)^3$ then the next digit $d$ will have to verify $(10a+d)^3 \le 10^3 N <(10a+d+1)^3$.
So that we want the largest digit $d$ such that $\left(30a(10a+d)+d^2\right)d \le 10^3(N-a^3)$.

To get a feeling of this method let's evaluate $\sqrt[3]{2}$ starting with $N=2,\ a=1$ :

$ \begin{array} {r|l} 2.000.000 & 1\\ \hline \\ -1.000.000 & 1.25\\ 1.000.000 & \\ -728.000 & \\ 272.000 & \\ -225.125 & \\ 46.875 & \\ \end{array} $

$a=1$ so that the first decimal must verify $(30(10+d)+d^2)d \le 1000$ that is $d=2$.
$a=12$ and the second decimal must verify $(360(120+d)+d^2)d \le 272000$ so that $d=5$.
(let's notice that this is 'nearly' $360\cdot 120\cdot d \le 272000$ so that $d=5$ or $d=6$ : we don't really need to try all the digits!)

I could have continued but observed that for $d=6$ the evaluation returned $272376$ so that the relative error on $d$ is $\epsilon_1 \approx \frac{376}{272376+360\cdot 6^2}\approx 0.001318$ giving $d\approx 5.9921$ and the solution $\sqrt[3]{2}\approx 1.259921$.


Now let's give a chance to Nirbhay Sngh Nahar's method exposed here.

Let's consider $N=2000$ then $x=1\cdot 10=10$

The NAHNO approximative formula is : $$A= \frac 12\left[x+\sqrt{\frac{4N-x^3}{3x}}\right]= \frac 12\left[10+\sqrt{\frac{4\cdot 2000-10^3}{3\cdot 10}}\right]\approx 12.6376$$

Doesn't look very good... Let's give the formula a second chance by providing a much better value of $x=12.5$ then the formula returns $A=12.5992125$ not so far from $2^{\frac 13}= 12.59921049894873\cdots$ but $x=12.5$ is really near the solution so let's compare this method with Newton's iterations $\displaystyle x'=x-\frac{x^3-N}{3x^2}$

$x_0=12.5\to x_1=12.6\to x_2=12.599210548\cdots \to x_3=12.5992104989487318\cdots$

EDIT: I missed the 'Precise Value of Cube Root' using following formula : $$P=A\frac{4N-A^3}{3N}$$ (I updated the picture and added this formula as well as the third Newton iteration)

The NAHNO approximative formula is better than the first Newton iteration but weaker than the second. The precise NAHNO formula is beaten only by the third Newton approximation as you may see in this picture (the curves are from top to bottom : first Newton iteration, Approximative NAHNO, second Newton iteration, Precise NAHNO, third Newton iteration ; the NAHNO curves are darker, the vertical scale is logarithmic and 'lower is better') :

log|relerror|

The vertical axis shows $\ \log \left| \frac {A(N)}{N^{\frac 13}}-1\right|$ for $N$ in $(1000,50000)$. The vertical lines are values $N$ such that $2\sqrt[3]{N}$ is integer (when the initial estimation is nearly the solution).

So that, considered as approximate formulas, NAHNO formulas are rather good and could be made more precise with a better first approximation (especially for $x$ between $1$ and $2.5$ more values should be provided in the table). Avoiding extravagant claims could be an advantage too! :-)

share|improve this answer
    
The first NAHNO formula appears to be identical to Halley's "irrational formula", as found for example in John Bonnycastle, The Scholar's Guide to Arithmetic, p. 150 (London 1851), accessible via Google Books: books.google.com/… –  njuffa Dec 7 '13 at 23:54
    
Interesting (and downloadable) book and reference. Thanks to share @njuffa ! –  Raymond Manzoni Dec 8 '13 at 0:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.