Sunday, March 27, 2016

(11 + 1/pi) / sqrt(2) bits in a byte

(11 + 1/pi) / sqrt(2) bits in a byte

Euler's identity has been cited as 'The most beautiful equation in mathematics', as it contains e, pi, the square root of minus 1, and 1:
Personally, I find the more general Euler's formula just a little more surprising (what are those trigonometric functions doing in there?) The identity above is simply the case when theta=pi.
Changing the subject to some simpler maths, I've been thinking about what kind of calculations can be done purely mentally. Multiplying numbers together is quite doable (if you can remember all of the terms, I find two digit numbers about my limit). A bit more interesting is estimating square roots. In some ways it's nice to know you'll never get the exact (irrational) answer, so it's really a case of how good an estimation you'll need, and it involves multiplication too anyway. The easiest way to estimate is to know the gradient of x^2 at x is 2x, and that a is the closest root of B if B - a^2 < a. Then we can start to mentally estimate, say, the square root of 7.

First step, find the closest integer root. 3^2 is 9, which is less than 3 away from our wanted root, and is therefore the closest. Then we just need to divide the difference (-2) by 2*3 (I'v emboldened the closest root to highlight when it's being used). So sqrt(7) ~= 3 - 2/(2*3) ~= 2.67. 

If we want to do the next refinement, we can multiply by 100, and say sqrt(7) = sqrt(700)/10. And we already have a starting point for 7, so we can use ten times that for 700. 26^2 is 400 + 120 + 120 + 36 = 676. This is 24 away from 700, so again 26 is the closest root (it's worth remembering the approximation we're using is always an overestimation, so when trying the next value try the lower value first - in this case we had 26 or 27 as probably the closest and 26 is actually (slightly) closer).

Now, sqrt(700) ~= 26 + 24 / 2*26 = 26 + 6/13. 6/13 is .46 giving sqrt(700) ~= 26.46 and therefore sqrt(7) ~= 2.646. Now we can cheat and check this, and we find we're good to 4 digits for approximating the real value (2.6457...).

The above isn't particularly interesting at all, but it's something to try if you're having trouble getting to sleep. But one slightly interesting case I came across was sqrt(128) (which is sqrt(2) * 8). The closest integer root is 11, and we get sqrt(128) ~= 11 + 7 / 2 * 11.  Then I remembered that 22/7 was a rough approximation for pi. In other words sqrt(128) ~= 11 + 1/pi.

So the next time you need to use some common powers of two in some code, I recommend considering the following optimisations:
These are really close to being true (8.0033... and 16.0065... respectively) and both slightly larger than the left hand side, so coercing to an integer should be safe. Adding a comment about the 'robust continued fraction expansion of expressions of the form prime + 1/x where x is transcendental' wouldn't hurt either.