Finding $n$-th root using only square root operation by finding the binary equivalent expression.

Question

It is given in the text of 'Polynomia And Related Realms', by Dan Kalman, that to efficiently approximate the $5$-th root using only the square-root key; need find the binary equivalent expression for $\frac{1}{5}$. So, $\frac{1}{5} = .001100110011\dots$ It is stated that the digits of the binary expansion are the coefficients of powers of $\frac{1}{2}$ rather than powers of $\frac{1}{10}$.

I am not clear about that : the binary expansion is in base $2$, & as all bits (binary digits) are in the fractional part, so in powers of $\frac{1}{2}$. So, does the author mean that need multiply by $\sqrt{2}$ the decimal expression : $.001100110011\dots\approx.00110011= 10^{-3}+10^{-4}+10^{-7}+10^{-8}$, leading to $\sqrt{2}(10^{-3}+10^{-4}+10^{-7}+10^{-8})$.

Answer 1

The representation of a fraction in binary is just like the representation of a fraction in decimal, except that it uses powers of two instead of powers of ten.

$$.00110011\dots = 2^{-3}+2^{-4}+2^{-7}+2^{-8}+\dots = \frac{3/16}{15/16}=\frac{1}{5}$$

by the formula for the sum of a geometric series.

Answer 2

In base 2 we have $$ a^{0.00110\dots_2} = a^{0/1}a^{0/2}a^{0/2^2}a^{1/2^3}a^{1/2^4}a^{1/2^5}\cdots $$ for any number $a>0$ because $$ 0.00110\dots_2 = 0/1+0/2+0/2^2+1/2^3+1/2^4+1/2^5+\dots $$ You can do the same in base 10: $$ a^{3.1415\dots_{10}} = a^{3/1}a^{1/10}a^{4/10^2}a^{1/10^3}a^{5/10^4}\cdots $$ This just requires combining the meaning of the decimal or binary expansion (as a power series in the base) and using the fact $a^{x+y}=a^xa^y$ repeatedly.

Answer 3

How do you find the binary expansion of any fraction $\lambda$ with $0<\lambda<1$? Say you want $1/\pi$.

Step 1: multiply by $2$ and take the whole number part, either $0$ or $1$. That’s your first bit. Then take the fractional part, and…

Step $n$: multiply by $2$ and take…

For $1/\pi$, I get: $.01010001\dots$