I have just finished solving an exercise from TAOCP and when I checked the answer I was surprised to see that it was correct. I was also extra-surprised by an application of the result suggested by Knuth.

Here are the first few Fibonacci numbers, that any programmer should know: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.

We can use these to mentally transform miles to kilometers and viceversa. How many miles are in 120km? Well 120 = 89 + 21 + 8 + 2. The equivalent in miles is 55 + 13 + 5 + 1 = 74. How to keep track of so many numbers in your head at once? Well, you really need to keep track of four numbers at any point in time. I'll illustrate for the conversion into miles of 350km. What is the biggest Fibonacci number not exceeding 350? Well, the first 277km are about 144miles. We are left with 73km and we repeat. The next 55km are about 34miles for a total of 178miles. We are left with 22km. The next 21km are about 13miles for a total of 191miles. And we are left with 1km which is about 1mile. The answer is 192miles.

Of course the transformation is not exact because the ratio mile/km is not exactly the golden ratio. It also works best for distances lower than 200.

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.