Category: mathematics


16 March Paul Hankin / computer science / mathematics

This post provides a quick derivation of the fast Fibonacci doubling formulas, using the correspondence between Fibonacci numbers and the number of ways to climb $n$ steps taking 1 or 2 steps at a time.

The Fibonacci numbers are a sequence $\mathrm{Fib}(i)$ defined by $\mathrm{Fib}(1)=\mathrm{Fib}(2)=1$ and $\mathrm{Fib}(n+2)=\mathrm{Fib}(n+1)+\mathrm{Fib}(n)$.

The Fibonacci doubling formulas are:

$$\begin{eqnarray} \mathrm{Fib}(2n) &=& 2\mathrm{Fib}(n)\mathrm{Fib}(n+1) - \mathrm{Fib}(n)^2 \\ \mathrm{Fib}(2n+1) &=& \mathrm{Fib}(n+1)^2 + \mathrm{Fib}(n)^2 \end{eqnarray}$$

These formulas can be used to efficiently compute Fibonacci numbers (see the the end of the post for how). They are usually derived from a matrix power representation of Fibonacci numbers (or see one of my earlier posts for an alternative). This blog post gives a direct combinatorial derivation.

10 June Paul Hankin / mathematics / game theory

This article describes how to use the Kelly criterion to make rational choices when confronted with a risky financial decision, and suggests a way to estimate the most you should be willing to pay for any particular sort of insurance.

The Kelly criterion (which at its core is the idea that the logarithm of your wealth is a better measure of money’s value to you than its absolute value) is well understood by the informed gambling community, and should be more widely known.

If you decide to apply the knowledge in this post, also consult with a financial professional (which as we’ll see later doesn’t include most finance or economics students, and most young financial professionals), and read the disclaimer at the end.

14 May Paul Hankin / computer science / mathematics

An earlier post described how to compute Fibonacci numbers in a single arithmetic expression.

Faré Rideau, the author of a page of Fibonacci computations in Lisp, suggested in a private email a simple and efficient variant, that I believe is novel.

For $X$ large enough, $\mathrm{Fib}_n = (X^{n+1}\ \mathrm{mod}\ (X^2-X-1))\ \mathrm{mod}\ X$.

That means you can compute Fibonacci numbers efficiently with a simple program:

for n in range(1, 21):
    X = 1<<(n+2)
    print(pow(X, n+1, X*X-X-1) % X)

This blog post describes how this method works, gives a few ways to think about it, easily infers the fast Fibonacci doubling formulas, provides a nice alternative to Binet’s formula relating the golden ratio and Fibonacci numbers, and expands the method to generalized Fibonacci recurrences, including a near one-line solution to the problem of counting how many ways to reach the end-square of a 100-square game using a single six-sided dice.

27 April Paul Hankin / mathematics / computer science

This code, somewhat surprisingly, generates Fibonacci numbers.

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

In this blog post, I’ll explain where it comes from and how it works.