Irreal

Here’s a very nice discussion of branch prediction from a Stack Overflow question. We graybeards and, really, just about everyone else like to pretend that all processors are still like the PDP-11. They were easy to understand and their semantics easy to assimilate.

Modern processors are nothing like them, of course. Instead of a linear pipeline of instructions executed sequentially, modern processors like to gamble. They look ahead in the instruction stream and precalculate results so they’re ready when they’re needed. The difficulty arises when there’s a branch. What should the look ahead procedure do? Should it take the left fork or the right one.

It’s a difficult problem but there are, in fact, some effective procedures. It basically boils down to noticing what the average behavior is and betting on that. If the behavior is reasonably normal, the results are good. Most times the processor guesses right and there’s no reason to stop everything and back up like there is when the processor guesses wrong.

If you’re writing in Python or a similar high-level language, there’s no reason to worry about this. But if you’re writing in C, or some other low-level language, this is something you sometimes have to take into account.

Happily, most of us don’t have to worry about such things but it’s worth knowing that the problem exists if only to have them in the back of our minds as we write our code.

Peteris Krumins has a nice post on using Fibonacci numbers to covert between miles and kilometers. The TL;DR is that if you take any two consecutive Fibonacci numbers, X and Y, there will be approximately Y kilometers in X miles (and vice versa, of course). The approximations are amazingly precise.

There’s more. The above works only if the number you want to convert is a Fibonacci number but you can express the number you do want to convert as a sum of Fibonacci numbers and sum up the corresponding pair numbers to get the conversion. Take a look at Krumins’ post for an example.

It’s not an accident that it works, of course. The secret is the ratio of consecutive Fibonacci numbers, \(F_{n+1} / F_{n}\) converges to the Golden Ratio, \(\frac {1+\sqrt{5}} {2} \approx 1.618034\). The key is that there are 1.609344 kilometers per mile, which is very close to the Golden ratio.

Serendipitously, John Cook, a Mathematician, has a recent post on the same subject. He makes an interesting observation. The higher the value of n the closer \(F_{n+1} / F_{n}\) gets to the Golden Ratio so, naively, one expects the kilometer-mile approximation to get better too. That works for a while, but for larger n, the \(F_{n+1} / F_{n}\) ratio gets closer to the Golden Ratio than the number of kilometers per mile. Cook calculates where the ratio is the best approximation to kilometers per mile and, surprisingly, it’s at 21/13, a lower number than I would have expected.

Cook also mentions Lucas numbers, which are very similar to Fibonacci numbers except for the starting values. It turns out that Lucas numbers provide an even better approximation but, really, both methods are back of the envelope approximations so who cares.

Perhaps I find this interesting only because I’m a Mathematician but I’m pretty certain the average Irreal reader will find it so too.