Rational Approximations

October 3, 2017

Finding rational approximations to real numbers may help us simplify calculations in every day life, because using $\displaystyle \pi=\frac{355}{113}$

makes back-of-the-envelope estimations much easier. It also may have some application in programming, when your CPU is kind of weak and do not deal well with floating point numbers. Floating point numbers emulated in software are very slow, so if we can dispense from them an use integer arithmetic, all the better.

However, finding good rational approximations to arbitrary constant is not quite as trivial as it may seem. Indeed, we may think that using something like $\displaystyle a=\frac{1000000 c}{1000000}$

will be quite sufficient as it will give you 6 digits precision, but why use 3141592/1000000 when 355/113 gives you better precision? Certainly, we must find a better way of finding approximations that are simultaneously precise and … well, let’s say cute. Well, let’s see what we could do.

Binet’s Formula

December 13, 2016

You will encounter a large number of formulas in your life, and quite many of them just seem to come out of the blue. That’s fortunately quite false, despite it being not always easy to retrace the formulas’ authors’ steps. One that appears as suspicious as it seems magic, is Binet’s Fibonacci Number formula: $\displaystyle F_n=\frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$,

where $\displaystyle\phi=\frac{1+\sqrt{5}}{2}$

is the golden number.

But it’s not quite out of nowhere, and, if you know how to solve recurrences using the characteristic equation, it’s in fact quite straightforward. Let’s see how.

A random Golden Ratio Appears!

November 12, 2013

Well, we all make errors once in a while, but sometimes they’re more interesting than others. So I inadvertently forgot a square in a calculation and the series suddenly started converging, to the most beautiful of convergences of all: $\phi$. So, let’s see how I got the golden ratio to emerge from a broken algorithm.

Hash Table and Magic (Relatively Primes) Numbers

September 17, 2013

Today, let’s talk about hash tables. Or, more precisely, one type of secondary probing technique, one that uses some number theory—but not quadratic residues, just relatively prime numbers. I don’t know if you’re like me, but it often bugs me when I read something in a textbook that seems to make sense, but is claimed without proof nor demonstration (oh, I think I said that before). That seems to happen particularly often when I read stuff about data structures, and this time I decided to explore one of those claims.

Cats, Pharaohs, and the Golden Ratio

December 8, 2009

Certain numbers keep showing up in nature. The Golden Ratio, $\phi \approx \displaystyle\frac{1+\sqrt{5}}{2}$

is one of them. It shows up in cats, sunflowers, and Egyptian pyramids. 