Faster methods for finding binary reciprocals by hand

43 Views Asked by At

Are there any faster methods than long division for finding the binary expansion of a reciprocal by hand? I've noticed some patterns, such as $\frac{1}{2^n-1} = 0.\overline{[n - 1\text{ 0s}]1}$ and $\frac{1}{2^n+1} = 0.\overline{[n\text{ 0s}][n\text{ 1s}]}$, which speed up certain reciprocals, but only apply to a small amount of them. I've been unable to find patterns that apply to other reciprocals.

I'm attempting to calculate Pi to high precision by hand, which with the series I'm using requires calculating binary reciprocals for many numbers. Any speedup in the process would greatly decrease the time it takes. I'm not super knowledgeable in math, so apologies if this is a bad question.

1

There are 1 best solutions below

3
On

This answer ended up being kind of long. So if you want to see the process, jump to the summary at the end.

Denominators of the form $2^n - 1$

When we write a real number $x \in [0, 1]$ as a sequence of bits $(b_1, b_2, \dots)$, where each $b_i \in \{0, 1\}$, what we are really doing is expressing it as the sum of the series $$ x = \sum_{i=1}^{\infty} \frac{b_i}{2^i}. $$

As I'm sure you know, this sequence is eventually periodic if and only if the number is rational. For instance, you've observed that in binary, with $n = 3$, \begin{align} 0.\overline{001} &= 0.001001001001\dots \\ &= 0.001 + \frac{0.001}{1000} + \frac{0.001}{1000^2} + \frac{0.001}{1000^3} + \cdots \\ &= 0.001 \cdot \biggl(1 + \frac{1}{1000} + \frac{1}{1000^2} + \frac{1}{1000^3} + \cdots \biggr) \end{align} And in decimal, this looks like $$ \frac18 \cdot \biggl( 1 + \frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3} + \cdots \biggr) = \frac{1}{8} \cdot \frac{1}{1 - \frac{1}{8}} = \frac{1}{8 - 1} = \frac{1}{7}, $$ which fits your pattern with blocks of length $n = 3$ since $2^3 - 1 = 7$.

It's clear that this calculation generalizes to show, in binary, that $$ 0.\overline{\underbrace{0\dots0}_{n-1}1} = \underbrace{0\dots0}_{n-1}1 \cdot \biggl(1 + \frac{1}{1\underbrace{0\dots0}_{n-1}} + \frac{1}{{1\underbrace{0\dots0}_{n-1}}^2} + \frac{1}{{1\underbrace{0\dots0}_{n-1}}^3} + \cdots \biggr), $$ or in decimal $$ \frac{1}{2^n} \cdot \biggl( 1 + \frac{1}{2^n} + \frac{1}{2^{2n}} + \frac{1}{2^{3n}} + \cdots \biggr) = \frac{1}{2^n} \cdot \frac{1}{1 - \frac{1}{2^n}} = \frac{1}{2^n - 1}. $$

Denominators of the form $2^n + 1$

For numbers of the form $2^n + 1$, your observed pattern holds because $$ (2^n + 1)(2^n - 1) = 2^{2n} - 1, $$ which is again of the previous form, so \begin{align} \frac{1}{2^n + 1} &= \frac{2^n - 1}{2^{2n} - 1} \\ &= \frac{2^n - 1}{2^{2n}} \cdot \frac{1}{1 - \frac{1}{2^{2n}}} \\ &= \frac{2^n - 1}{2^{2n}} \cdot \biggl( 1 + \frac{1}{2^{2n}} + \frac{1}{2^{4n}} + \frac{1}{2^{6n}} + \cdots \biggr) \\ &= (2^n - 1) \; \biggl( \frac{1}{2^{2n}} + \frac{1}{2^{4n}} + \frac{1}{2^{6n}} + \frac{1}{2^{8n}} + \cdots \biggr), \end{align} which describes a bit sequence of repeating blocks of length $2n$, where the block is the binary representation of $2^n - 1$, i.e. a string of length $$ \underbrace{000\dots000}_{n}\underbrace{111\dots111}_{n} $$

Other denominators

It depends on the factorization of the denominator. As the $2^n + 1$ case shows, the goal is to rearrange the fraction to have a denominator of the form $2^m - 1$ for some $m$, where we know the pattern of bits.

Let's work out a bigger example, say $x = \frac{1}{11}$. Clearly, $11 \neq 2^n - 1$ for any natural $n$, but $$ \frac{1}{11} = \frac{2}{22} = \frac{3}{33} = \cdots $$ and maybe some number in the sequence $(11, 22, 33, \dots)$ is of the form $2^n - 1$. In other words, we want to find some natural $k$ such that $11k = 2^n - 1$, or equivalently, $2^n = 11k + 1$. So we can look at the powers of $2$ until we find one that's one more than a multiple of $11$. So we're interested in residues modulo $11$ in the doubling sequence: $$ \begin{array}{c|cccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2^n \bmod{11} & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \end{array} $$

As you can see $2^{10} = 11k + 1$, and it turns out that $1023 = 11 \cdot 93$. This means that we can write $$ \frac{1}{11} = \frac{93}{93 \cdot 11} = \frac{93}{2^{10} - 1}. $$ We can convert $93$ to binary (e.g., via the the algorithm of repeated halving and recording remainders), obtaining $1011101$. Since $n = 10$, this means that the bit string will consist of repeating blocks of length $10$ so we pad it out, obtaining $$ 0.\overline{0001011101} $$

Why does this work?

First of all, notice that there's nothing special about beginning with a numerator of $1$, as we have to represent the fraction (possibly no longer in lowest terms) with a denominator of the form $2^n - 1$.

But there's one potential hitch: if the denominator $q$ is even. In this case, every power of $2$ is congruent to an even residue modulo $q$. But, that's okay, we just have to do a bit of pre-processing. Factor out the largest power of $2$ first (it will just be a bit shift to the final binary representation): $q = 2^s q'$, where $q'$ is odd, so $$ \frac{p}{q} = \frac{1}{2^s} \cdot \frac{p}{q'}, $$ and we work with $q'$ as before.

For example, if $\frac{p}{q} = \frac{1}{88}$, write $$ \frac{1}{88} = \frac{1}{2^3} \cdot \frac{1}{11}, $$ so $q' = 11$, and the binary representation is obtained from the example above but shifted $s = 3$ digits to the right: $$ 0.\underbrace{000}_{s=3}\overline{\underbrace{0001011101}_{n=10}} $$

So, assuming without loss of generality that the denominator is odd, the remaining question is: how do we know that such an $n$ can be found. It turns out that the sequence of residues $(2, 2^2, 2^3, \dots) \bmod{q}$ must eventually reach $1$. The number $n$ that measures the length of the repeating block of bits is the order of $2$ in the multiplicative group of units of the finite cyclic group $C_q^\times$, and in fact $n$ must be a divisor of $\varphi(q)$, where $\varphi$ is Euler's totient function.

Summary

  1. Say that $x = \frac{p}{q}$ a rational number in $[0, 1]$ in lowest terms, i.e., $0 \leq p \leq q$ and $\gcd(p, q) = 1$.

  2. If $q = 2^s$ for some $s \geq 1$, then the binary representation is $$ 0.\underbrace{0\dots0}_{s-1}1 = 0.\underbrace{0\dots0}_{s-1}1\overline{0} $$

  3. Else write $q = 2^sq'$, where $q'$ is odd.

  4. Find the smallest $n$ such that $2^n \equiv 1 \pmod{q'}$.

  5. Convert $p$ to binary (less than $n$ bits guaranteed): $$ p = \sum_{j = 0}^{n-1} \frac{b_j}{2^j} $$

  6. Write down binary representation of $$ \frac{p}{q} = \frac{1}{2^s} \cdot \frac{p}{q'} = \frac{1}{2^s} \cdot \frac{p}{2^n - 1} $$ as $$ 0.\underbrace{0\dots0}_{s}\overline{\underbrace{b_{n-1}\dots b_1b_0}_n} $$