1

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})$.

jiten
  • 4,524

3 Answers3

2

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.

saulspatz
  • 53,131
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.

Joonas Ilmavirta
  • 25,809
1

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$

Lubin
  • 62,818