Finding iteratively approximation of cube root with square root operation

Question

It is given in the paper titled: A Simple Calculator Algorithm by: Lyle Cook, James McWilliam; the way to iteratively find using the cube root using the square root operation is to perform the set of two operations alternatively: (i) Take the square root twice; (ii) multiply by the original number, ...

I want to know first why this approach is deemed useful, i.e. on what basis. It is also stated on the last page(#54) that a better way is to take the square root thrice, instead of twice. So, what is the reason for taking $y^\frac{1}{2\sqrt 2}$. (sorry, if not represented root properly, request correct way then)

Second, I tried to find the value obtained by program, by giving inputs : $57, 24, 8$. Request suggestions for improvements.

Answer 1

First addressing why it is useful, well, first it's a good party trick with a basic calculator without a $x^y$ button.

Alice: "If a calculator only has $\sqrt{}$, some numbers, and multiplication, what can you compute or approximate?"

Bob: "Obviously, the square root and multiplication"

Alice: "What if I can estimate the cube root of any number that you give to me? "

Bob:" Is it some sort of binary search, that is trivial isn't it?"

and then Alice gets to perform this trick. What is even cooler is

In theory, it is possible to approximate any real root using a calculator with a square root key.

Alright, now, going on to the maths:

Starting from $x_1=r$,

Define:

$$x_{k+1} =(x_k+1)r$$

We can easily prove by induction that this is just a geometric series with the first term being $r$ and common ratio $r$,$$x_{k+1}= \sum_{i=1}^{k+1}r^i=\frac{r(1-r^{k+1})}{1-r}$$

Hence as $k \to \infty$, if $|r|<1, r \ne 0$, $$x_{k+1} \to \frac{r}{1-r}=\frac{1}{\frac1r-1}$$

If we pick $r= \frac14$, then the sequence converges to $\frac1{4-1}=\frac13$.

If we pick $r = \frac1{2^n}$, then the sequence converges to $\frac1{2^n-1}$

and we have $y^{x_k} \to y^{(\frac1r-1)^{-1}}.$ If we pick $r = \frac14$, then $y^{x_k} \to y^\frac13$.

Taking square root twice means $\frac14$ at the power indices and multiply by itself once means plus $1$ in the power index.

Comments about your program:

• There isn't a need to store every single values in a matrix if the purpose is just to print it.
• In the presence of a well established approximated solution, rather than asking for maximum number of iterations, perhaps just ask for the error tolerance and use a while loop to terminate when the error tolerance is satisfied.

Comments on comparison between bisection and this method:

For binary search that begins with interval length $1$: to shrink it up to $10^{-8}$. We need $8\log_2 10 \approx 26.5$ steps.

For this method.

Note that $x_k$ increases.

We want $$57^\frac13-57^{x_k}< \epsilon$$ $$\log_{57}(57^\frac13 - \epsilon) <{x_k}$$

$$ \frac{r}{1-r}(1-r^k)> \log_{57}(57^\frac13 - \epsilon)$$

$$r^k < 1- 3\log_{57}(57^\frac13 - \epsilon)$$ $$4^k > \frac{1}{ 1- 3\log_{57}(57^\frac13 - \epsilon)}$$

$$k > - \log_4 ( 1- 3\log_{57}(57^\frac13 - \epsilon))$$

From the computation $k$ needs to be at least $15$ which is reflected in your computation.

This method is faster when

$$-\log_4 ( 1- 3 \log_y ( y^{\frac13}-\epsilon) < - \log_2 \epsilon$$

$$ 1- 3 \log_y ( y^{\frac13}-\epsilon) > \epsilon^2$$

$$ \frac{1- \epsilon^2}3 > \log_y ( y^{\frac13}-\epsilon) $$

$$ y^{\frac13} - y^{\frac{1-\epsilon^2}3}< \epsilon$$

Answer 2

As explained in the paper, it is based on the infinite sum of geometric progression: $\sum_1^\infty(1/4)^n=1/3$. The number that you get after taking square root twice at each iteration is an approximation of the cubic root. I am not sure why they are suggesting to take the square root thrice, I do not think it's going to be an improvement.

Answer 3

An algorithm producing the cubic root of $x$ positive starts from $x_0=y_0=x$ and iterates the steps:

• Compute $x_{k+1}=\sqrt{\sqrt{y_k}}$
• Compute $y_{k+1}=x_{k+1}x$

Then, indeed, $$\lim x_k=x^{1/3}$$ because $$\frac14\left(1+\frac14+\frac1{4^2}+\frac1{4^3}+\cdots\right)=\frac13$$

Likewise, the algorithm starting from $u_0=v_0=x$ and iterating the step:

• Compute $u_{k+1}=\sqrt{\sqrt{\sqrt{v_k}}}$
• Compute $v_{k+1}=u_{k+1}x$

yields $$\lim u_k=x^{1/7}$$ because $$\frac18\left(1+\frac18+\frac1{8^2}+\frac1{8^3}+\cdots\right)=\frac17$$