Fibonacci numbers

A Fibonacci number is the sum of the two previous numbers in the sequence. Write a function that finds the n-th Fibonacci number.

These are the first 10 fibonacci numbers: 1 1 2 3 5 8 13 21 34 55

Input:   5
Output:  5

Input:   12
Output:  144

Input:   200
Output:  280571172992510140037611932413038677189525

Solutions

The number of bits needed to represent the n-th fibonacci number scales linearly with n, so we need to consider an extra O(n) factor when considering time/space complexities.

For reference:

The 10th fibonacci number has 6 bits
The 100th fibonacci number has 68 bits
The 1,000th fibonacci number has 693 bits
The 10,000th fibonacci number has 6,941 bits

Solution	Time	Space
Recursion	O(2ⁿ n²)	O(n²)
Memoization	O(n²)	O(n²)
Dynamic programming	O(n²)	O(n²)
Iterative	O(n²)	O(n)
Binet's formula	O(n log n log log n) to O(n²)	O(n)
Fast doubling	O(n log n log log n) to O(n²)	O(n)

Solution 1: Recursion

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

Time	O(2ⁿ n²)	2 recursive calls adding O(n)-bit numbers at n levels
Space	O(n²)	O(n) max stack depth with O(n) bits for the nth number

Solution 2: Memoization

def fibonacci(n, cache = [])
  return n if n <= 1
  return cache[n] unless cache[n].nil?
  cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
end

Time	O(n²)	O(n) stack depth adding O(n) bit numbers
Space	O(n²)	n-sized array of numbers with O(n) bits per number

Solution 3: Dynamic programming

def fibonacci(n)
  numbers = Array.new(n + 1)
  numbers[0] = 0
  numbers[1] = 1
  (2 .. n).each do |i|
    numbers[i] = numbers[i - 1] + numbers[i - 2]
  end
  numbers[n]
end

Time	O(n²)	O(n) loop adding O(n)-bit numbers at each iteration
Space	O(n²)	n-sized array of numbers with O(n) bits per number

Solution 4: Iterative

def fibonacci(n)
  a, b = 0, 1
  n.times do
    a, b = b, a + b
  end
  a
end

Time	O(n²)	O(n) loop adding O(n) bit numbers at each iteration
Space	O(n)	Two integers each containing O(n) bits

Solution 5: Binet's formula

Calculating a fibonacci number with this formula uses log(n) multiplications when using exponentiation by squaring, which results in a time complexity bounded by the runtime of the multiplication algorithm being used:

Runtime	Algorithm
O(n²)	Regular long multiplication
O(n^1.585)	Karatsuba algorithm
O(n^1.465)	3-way Toom-Cook multiplication
O(n log n log log n)	Schonhage-Strassen algorithm

In the worst case, multiplication is done by multiplying each digit together and summing them up. The runtime is O(n²), but in practice this algorithm is slower than the O(n²) addition algorithms because of performance penalties in floating-point arithmetic vs adding integers.

The best case happens with the Schonhage-Strassen algorithm, which starts to outperform the other algorithms at astronomically large values of n with tens-of-thousands of digits.

The floating point precision of standard libraries in most programming languages are not enough to handle the precision needed for large numbers of n. You'll need to use a library designed to handle unlimited precision like the GNU multiple precision arithmetic library if you want accurate calculations as n increases in size.

require 'gmp'

def fibonacci(n)
  precision = [16, (0.8*n).to_i].max
  sqrt_5 = GMP::F.new(5, precision).sqrt
  phi = (sqrt_5 + 1) / 2
  GMP::Z.new(phi**n / sqrt_5)
end

Time	O(n log n log log n) to O(n²)	Varies depending on the multiplication algorithm used
Space	O(n)	Floating point numbers each of size O(n)

Solution 6: Fast doubling

Same runtime as Binet's formula above, but operating only on integers, so there's no need for an arbitrary floating point precision library.

def fibonacci(n)
  tuples = lambda do |n|
    return [0, 1] if n == 0
    a, b = tuples.call(n / 2)
    c = a * (b * 2 - a)
    d = a ** 2 + b ** 2
    if n % 2 == 0
      [c, d]
    else
      [d, c + d]
    end
  end
  tuples.call(n).first
end

Time	O(n log n log log n) to O(n²)	Varies depending on the multiplication algorithm used
Space	O(n)	Integers of size O(n)

Level Order