Mentally multiply by π

I recently came across this interesting article (blog post?) from the Fediverse showing a nifty trick to compute multiples of π by relying on only two products: by 3, and by 14. I encourage you to read the article if you're interested in the method because it's crystal clear, whereas I'm going to muddy the waters a bit, throwing my considerations at it.

The reason why the proposed idea works is that the first digits of the fractional part of the decimal expansion of $\pi$ can be expressed as multiples of 14. Indeed, the fractional part of $\pi =3.14159265359...$

This effectively means that

$$\pi =3.14159265359...=3+14\cdot {10}^{-2}+14\cdot {10}^{-4}+14\cdot {10}^{-5}+...$$

and thus

$$k\cdot \pi =3k+14k\cdot ({10}^{-2}+\cdot {10}^{-4}+\cdot {10}^{-5}+...)$$

which is interesting because ${10}^{-x}$ means “shifting your results right by $x$ digits”, which is particularly nice if $k$ is an integer up to 7, and thus $7k$ has two digits, and the first two terms in the expansion are shifted by two and four digits (no need to take any actual summation).

Let's make the example with $k=7$, and try to compute

$$7\pi =21.991148575...$$

This may seem to be an arbitrary divergence from Cook's example, but is actually needed to discuss one of the limitations of the approach: spillover. We have $3k=21$, $14k=98$, and thus the first terms (up to what Cook's calls the simplest approach) are:

$$7\pi \approx 21.9898$$

(relative error is $<6.2\cdot {10}^{-5}$ —note that this is the same found by Cook, even though he discusses the absolute error instead)

Things get a bit hairier on the first refinement, because the value of $14k$ now needs to be shifted by one more digit, not two. And while in Cook's example with $k=4$ he has $14k=56$ and $560+56=616$ (remove the last two digits, replace with the new three digits) in our case there's a bit of a spillover: $980+98=1078$, so this refinement doesn't lend itself to a simple substitution of the last two digits:

$$7\pi \approx 21.99078$$

(relative error $<1.7\cdot {10}^{-5}$.)

The next refinement is a bit more involved, because (you may notice the $7$ in the tableau at the top of this article) it involves halving our $14k$ —which, coincidentally, is always possible because $14$ is even— and adding it in the same place. In our case, this means adding another $49$ to the last two digits, and once again we have a small spillover (luckily into a $0$):

$$7\pi =21.99127.$$

The relative error is now $<5.6\cdot {10}^{-6}$, more than order of magnitude better than the initial result, and —interestingly— it is now an overestimation.

Alternatives

If you go read the Fediverse thread, you'll notice that I raised the question of the comparison with approximations compute from the well-known rational approximations of $\pi$, i.e.

$$\frac{22}{7}=3+\frac{1}{7}$$

and

$$\frac{355}{113}=3+\frac{16}{113}=3+\frac{1}{7}-\frac{1}{791}$$

Aside from the somewhat contrived case of $k=7$ I'm using here an example, multiples of these fractions would be harder to compute, as observed by Bill Ricker, although the multiple of $355/113$ would still be more accurate.

What is interesting is that the second refinement presented by Cook can be further refined, e.g. by replacing the last “half $14k$” contribution with a “3/8th of $14k$” contribution. This is less trivial to compute, unless we consider that $3/8=1/2-1/8$, so we can correct Cook's refinement by subtracting the “half $14k$ divided by 4”, which in our case is $49/4=12.25$.

Even if we truncate this to $12$, the fixup gives us

$$7\pi \approx 21.99115$$

with a relative error that is now $<6.5\cdot {10}^{-8}$, which is now two orders of magnitude lower. (The actual correction would be $7\pi \approx 21.9911475$ with a relative error $<5\cdot {10}^{-8}$.)

What is impressive about this particular result is that the relative error is not only of the same order as the one given by the $355/113$ approximation, but actually slightly better (the relative error for $355/113$ is closer to $8.5\cdot {10}^{-8}$).

A summary

To get a good approximation of a multiple of $\pi$:

1. multiply by 3 (call this $u$);
2. multiply by 14 (call this $f$);
3. add: $u$,
   $f$ shifted by 2 digits,
   $f$ shifted by 4 digits,
   $f$ shifted by 5 digits;
4. bonus: add
   $f/2$ shifted by 5 digits;
5. extra: subtract
   $f/8$ shifted by 5 digits
   (note that $f/8$ can be computed as $\left(\frac{f}{2}\right)/4$).

An alternative to the last two points, getting to the same results, would be to add $f/4+f/8$ (this time computing $f/8$ as half of $f/4$) shifted by 5 digits.

Let's apply to this to Cook's example for $4\pi$:

1. $4\times 3=12$;
2. $4\times 14=56$;
3. $12+0.56+0.0056+0.00056=12.56616$;
4. bonus: $56/2=28\Rightarrow 12.56644$
   (note that Cook's post has a couple of typos in this line; absolute error is still $<7\cdot {10}^{-5}$);
5. extra: $28/4=7\Rightarrow 12.56637$
   (absolute error is now $<6.2\cdot {10}^{-7}$; note that the extra division by 4 is particularly easy to do in Cook's example).

with the possibility to replace 4. and 5. with

$$\frac{56}{4}=14,\frac{14}{2}=7\Rightarrow 12.56616+0.00014+0.00007=12.56630+0.00007=12.56637.$$

Note however that $12.5663$ is slightly worse than $12.56644$ as an approximation (error $7.1\cdot {10}^{-5}$ rather than $<7\cdot {10}^{-5}$, in addition of being of the opposite sign.) Note also that the best approximation we've discussed so far ($12.56637$) is also the midpoint of these two.

Smallest doesn't mean easier to handle

I believe that one of the most important discoveries to which this trick has led me is the importance of the difference between the compactness of the (approximating) fraction and how easy it is to handle.

This isn't something entirely new to me (I've always known that in computing there are several series that help find out new digits of $\pi$ faster), but what I learned this time is how this maps to “human computing”.

If we write the full mathematical expression of the $\pi$ approximant that leads to the algorithm we just described we have:

$$\pi \approx 3+\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{1}{1000}\cdot (1+\frac{1}{2}\cdot (1-\frac{1}{4}))) (\star )$$

which is considerably more complex than the expressions we have from the continued fraction expansion,

$$\pi \approx \frac{22}{7}=3+\frac{1}{7}$$

or even my beloved Milü

$$\pi \approx \frac{355}{113}=3+\frac{16}{113}=3+\frac{1}{7}-\frac{1}{791}=3+\frac{1}{7}\cdot (1-\frac{1}{113}).$$

Yet, except for particular cases, the divisions by $7$ and $113$ involved in the latter expressions are likely to be more complex than the “multiply by $14$, divide by $100$”, because the division by $100$ in the decimal system is a simple shift by two digits.

To wit, if we have computed $1/7$ for the $22/7$ approximation, it would be simpler to approximate $\pi$ as

$$\frac{2199}{700}=3+\frac{1}{7}-\frac{1}{700}=3+\frac{1}{7}\cdot (1-\frac{1}{100})$$

than with the $355/113$ expansion, since the last term is obtained simply by shifting by two digits the already computed division by $7$. Even $3+1/7-1/800$ (more accurate, but still not as much as $355/113$) would be faster than the full $355/113$ contribution.

Sevenths

Incidentally, here's an interesting fact:

$$\frac{1}{7}=0.\left(142857\right)=\frac{14}{100}+2\cdot \frac{14}{{100}^2}+4\cdot \frac{14}{{100}^3}+8\cdot \frac{14}{{100}^4}+...$$

and if we factor $14/100$ (recognize it yet?)

$$\frac{1}{7}=\frac{14}{100}\cdot (1+\frac{2}{100}+\frac{4}{{100}^2}+\frac{8}{{100}^3}+\cdots )=\frac{14}{100}\cdot \sum _{i=0}^{\infty }\frac{2^i}{{100}^i}.$$

Now, if we compute $1/7(1-1/100)$ as discussed above, we get

$$\frac{1}{7}(1-\frac{1}{100})=\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{2}{{100}^2}+\frac{4}{{100}^3}+\cdots )$$

and you may notice that the first two terms are the same as the ones in the mind trick formula $(\star )$. Where they start to diverge is on the third term, which is $2/10000=1/5000$ here, but (after simplifications) $11/8000$ in the mind trick formula.

This divergence should not surprise, since $1/7-1/700$ is actually a pretty poor approximation for $\pi -3$. If we try $1/7-1/800$, the first terms are a bit more complex to compute:

$$\frac{1}{7}-\frac{1}{800}=\frac{1}{7}\cdot (1-\frac{7}{8}\cdot \frac{1}{100})=\frac{14}{100}\cdot (1+\frac{9}{8}\cdot \frac{1}{100}+\frac{25}{8}\cdot \frac{1}{{100}^2}+...)$$

but we can make it easier to compare with $(\star )$ by rearranging the terms as

$$\frac{1}{7}-\frac{1}{800}=\frac{14}{100}\cdot (1+\frac{1}{100}+\frac{1}{8}\cdot \frac{1}{100}+\frac{25}{8}\cdot \frac{1}{{100}^2}+...)$$

so that the third term would be:

$$\frac{100}{8}\cdot \frac{1}{{100}^2}+\frac{25}{8}\frac{1}{{100}^2}=\frac{125}{8\cdot 10000}=\frac{1}{8\cdot 80}=\frac{1}{640}$$

(compare $125/80000$ to the mind trick's $110/80000$.)

Speed versus accuracy

One of the key point in determining the approach to use to find approximate values to multiples of $\pi$ is to take into account the accuracy of the multiplier.

As an example, assume we want to compute the circumference of the Earth, knowing that the radius is approximately $r=6500$ km. We want to compute $2\pi r$ or $13000\pi$.

One would be tempted to use the magic algorithm that has been the main topic of discussion of this article, but that would actually be a waste of brainpower in this case, since the approximation for the radius is quite large already: there's no need to compute $13000\pi$ to particularly high accuracy, and in fact in this case the $3+1/7$ approximation of $\pi$ is sufficient: the first part is trivial, $3\times 13000=39000$, and the rest is

$$\frac{13000}{7}=\frac{14000}{7}-\frac{1000}{7}\approx 2000-140$$

(the next term from $1/7$ would be $140/100$, already too precise) which gives us a circumference of some $40960$ km.

The attentive reader who remembers when the meter was defined as the 40-millionth part of the circumference of the Earth, will have noticed that we're way over the expected $40000$ km, which is due to the fact that the (average) Earth radius is actually less than $6400$. If we want to redo these computations, this time with $12800\pi$, we have:

$$3\times 12800=38400$$

and leveraging the approximation $200/7\approx 28$:

$$\frac{12800}{7}\approx 1828$$

giving us a circumference of $38400+1828=40228$, which is still too large (and for the curious: no, using a more accurate approximation wouldn't solve the issue, dropping it only to around $40212$.)

Reciprocal problem

Maybe it would be better to work things the other way: assuming we know that circumference is $40000$ km, can we work out a more accurate value of the radius? This means computing $20000/\pi$. This is actually another one of those cases where the simpler, harder to manipulate fractions are easier to use, since their reciprocal is $1/\pi$.

In our case

$$\frac{20000}{\pi }\approx 20000\cdot \frac{7}{22}=\frac{70000}{11}\approx 6364$$

(the division by $11$ is easy to do in mind: $66$ from $70$ is $4$, $33$ from $40$ is $7$, and then it repeats). This is actually a pretty good approximation to the actual Earth radius, that is closer to $6371$ km. (Note also that using actual $\pi$ here would only give marginally better results with an integer part of $6366$: our approximation is accurate enough.)

So this got me wondering: could we build an approximant to $\frac{1}{\pi }$ that is as easy to handle as $(\star )$ and the corresponding algorithm? From a quick look, the answer seems to be … “ish”. We have

$$\frac{1}{\pi }=0.318309886...$$

so from a cursory look the best candidate to replace the $14/100$ in $(\star )$ is $318/1000$, and our shifts will be of three rather than two digits:

$$\frac{1}{\pi }\approx \frac{318}{1000}\cdot (1+\frac{1}{1000}\cdot (1-\frac{3}{100}))$$

which is considerably less manageable than $(\star )$, especially after the second term, because of the three-digit numbers, although it does give us pretty low relative errors right from the start, approximately $9.74\cdot {10}^{-4},2.55\cdot {10}^{-5},4.48\cdot {10}^{-6}$ at the first, second and third term.

A more manageable candidate may seem like $32/100$, since

$$\frac{1}{\pi }\approx \frac{32}{100}\cdot (1-\frac{1}{2}\cdot \frac{1}{100}-3\cdot \frac{1}{{100}^2}+\frac{2}{10}\cdot \frac{1}{{100}^2})$$

with relative errors of approximately $5.4\cdot {10}^{-3},2.8\cdot {10}^{-4},1.8\cdot {10}^{-5},1.6\cdot {10}^{-6}$ respectively for the first, second, third term, and fourth term. The big nuisance of this building block is that it seems to be built primarily around subtraction rather than addition, something which is harder to manage mentally compared to the “add by shift” of $(\star )$.

To compare let's try to compute the same $20000/\pi$ with the two approximations.

We have $2\cdot 318=636$, so the first two terms of using the $318/1000$

$$\frac{20000}{\pi }=10000\cdot \frac{2}{\pi }\approx 10000\cdot 0.636636=6366.36$$

(compare with actual result $6366.19772...$ to show the excellent result of this approximation.)

For $32/100$, we have $2\cdot 32=64$ and $3\times 64=252$, but:

$$\frac{20000}{\pi }=10000\cdot \frac{2}{\pi }\approx 10000\cdot (0.64-0.0032-0.000252+0.0000128)$$

that is:

$$\frac{20000}{\pi }=10000\cdot (0.64-0.003452+0.0000128)$$

and finally:

$$\frac{20000}{\pi }=6400-34.52+0.128=6365.48+0.128=6365.608$$

Ultimately, the fact that the expressions in this case are uglier and less manageable may just be the sign that computing the reciprocal of $\pi$ is an inverse problem. Or that I suck at these kind of things, especially at this hour.