A Linear Algebra Trick for Computing Fibonacci Numbers Fast

• mathlib4

  10 889 10.0 Lean

  The math library of Lean 4

  

We essentially implemented this matrix version in Lean/mathlib to both compute the fibonacci number and generate an efficient proof for the calculation.

https://github.com/leanprover-community/mathlib4/blob/master...

In practice this isn't very useful (the definition of Nat.fib unfolds quick enough and concrete large fibonacci numbers don't often appear in proofs) but still it shaves a bit of time off the calculation and the proof verification.

• fib-bench

  1 0 2.1 Ruby

  Benchmark of a few Ruby implementations of Fibonacci

I did this years ago to demonstrate that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/

Code winds up looking like:

  def fib_phi(n)

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• gmp-wasm

  38 12 10.0 C

  Fork of the GNU Multiple Precision Arithmetic Library (GMP), suitable for compilation into WebAssembly.

  

There are "bignum" implementations for every language. Though I never tested the performance impact on closed-form Fibonacci when a defined double precision >64bit is used.

https://gmplib.org/

Your code has an accidentally quadratic runtime (instead of linear). Since the array is appended to, the code regularly increases the memory region and has to move all the previous data over.

You could pre-allocate the memory as n is known ahead.

Suggest a related project