Perspective. As in the real world, by looking at a problem from a different angle, we can often find solutions much faster.

Day 12 is the matrix implementation of the fibonacci sequence. A specially constructed matrix has the property of calculating the next element in the sequence upon multiplication with the previous element.

Implementing the Fibonacci sequence like this has a rather special side effect: It allows reducing the problem of calculating the Fibonacci sequence to multiplication for which we can utilize knowledge on multiplication and make and calculate an element much faster than the iterative approaches.

The matrix looks like this:

$$ Q_{fib} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$

The nth element of the Fibonacci sequence can then be found by reading either the top-right or bottom-left element of the matric as defined by \( Q_{fib}^n \).

Let's see an example in Julia

❯❯❯ julia               _   _       _ _(_)_     |  Documentation: https://docs.julialang.org  (_)     | (_) (_)    |   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.  | | | | | | |/ _` |  |  | | |_| | | | (_| |  |  Version 1.8.1 (2022-09-06) _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release|__/                   |julia> Q = [1 1;1 0]2×2 Matrix{Int64}: 1  1 1  0julia> Q^102×2 Matrix{Int64}: 89  55 55  34

From here it is evident that the 10th element of the fibonacci sequence is 55.

Speeding up Calculations

As calculating the n'th element in the Fibonacci sequence is now the same as taking the exponent, we can utilize exponentiation by squaring. This method relies on the insight that \( b^n = b^{{2}^{n/2}} \) when n is even - a rule that can be derived from the power of a power rule:

$$ b^{{x}^{y}} = b^{x * y} $$

As an example we can calculate \( 2^{10} \) using the method:

$$ \begin{align*} 2^{10} &= 4^{5} \quad \text{(power of power rule)} \\ &= 4 \times (4^{4}) \\ &= 4 \times (16^{2}) \quad \text{(power of power rule)} \\ &= 4 \times 256 \\ &= 1024 \end{align*} $$

This algorithm can be implemented in Julia as the following:

function fast_exp(base, exp)  result = 1  while exp > 0    if exp % 2 == 0      base *= base      exp = exp ÷ 2    else      result *= base      exp -= 1    end  end  return resultend

And to see how well it works we can make a quick check on calculating the 100.000 element of the Fibonacci sequence.

...julia> include("fast-exp.jl")fast_exp (generic function with 1 method)julia> Q = [big(1) big(1);big(1) big(0)]2×2 Matrix{BigInt}: 1  1 1  0julia> @time fast_exp(Q, 100000);  0.000767 seconds (703 allocations: 285.633 KiB)julia> @time naive_exp(Q, 100000);  0.723526 seconds (3.10 M allocations: 4.097 GiB, 9.84% gc time)

The naive implementation is not the build in, rather the iterative implementation following the naive approach. The code can be found here.

Reduction and Abstraction

Key techniques when developing software is reduction and abstraction. The above is an example of a reduction to an algebraic field that allows us to use multiplication.