Indian claims finding new cube root formula

Solution 1:

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 Y₁, Y₂, Y₃, ... 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_j ³ and X, by defining Y_j+1 = Y_j + δ for a suitable increment δ; we then determine the error involved in the new approximation by computing Y_j+1³ = Y_j ³ + 3δY_j ² + 3δ²Y_j  + δ³. 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 = x₀ + x₁/8¹ + x₂/8² + ... , where each x_j ranges from 0 to 7. We compute binary digits y_j representing Y = y₀ + y₁/2¹ + y₂/2² + ...  such that Y³ = X, as follows.

• If x₀ = 0, set y₀ = 0; otherwise, set y₀ = 1. Let R := x₀ − y₀.

• Set A = B = C = y₀ .

• 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 x_j , x_j+1 , ... are also zero):

  1. Set D = 8R + x_j , and consider the largest binary digit y_j 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 y_j 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 y_j = 1; otherwise set y_j = 0.

  2. The integer A will actually be the number whose binary representation is the bit-sequence y₀ y₁ ... y_j−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 n^th 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).

Solution 2:

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') :

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! :-)

Solution 3:

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...

Solution 4:

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.