Skip to content

Instantly share code, notes, and snippets.

@ellcs

ellcs/fibbonacci.rb

Created April 27, 2020 09:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ellcs/3384a369b1e3b2efe05bc5879437cbfd to your computer and use it in GitHub Desktop.
Save ellcs/3384a369b1e3b2efe05bc5879437cbfd to your computer and use it in GitHub Desktop.
Download ZIP
Fast fibbonacci
Raw
fibbonacci.rb
# https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
N = (1 + Math::sqrt(5)) / 2
M = (1 - Math::sqrt(5)) / 2
def fibb(n)
(N**n - M**n) / (N - M)
end
# https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
require 'matrix'
def matrix_fibb(n)
Matrix[[1, 0]] * Matrix[[0,1], [1,1]]**(n) * Matrix[[0], [1]]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment