Skip to content

Instantly share code, notes, and snippets.

@havenwood
Last active October 24, 2016 23:32
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save havenwood/02cf291b809327d96a3f to your computer and use it in GitHub Desktop.
Save havenwood/02cf291b809327d96a3f to your computer and use it in GitHub Desktop.
nth fib with Matrix exponentiation in Ruby
require 'matrix'
def fib n
matrix = Matrix[[0, 1], [1, 1]] ** n.pred
matrix[1, 1].to_i
end
require 'minitest/autorun'
require 'minitest/pride'
describe 'fib' do
it 'does nth positive fib' do
assert_equal fib(0), 0
assert_equal fib(1), 1
assert_equal fib(2), 1
assert_equal fib(3), 2
assert_equal fib(4), 3
assert_equal fib(5), 5
assert_equal fib(6), 8
assert_equal fib(7), 13
assert_equal fib(8), 21
end
it 'does nth negative fib' do
assert_equal fib(-1), 1
assert_equal fib(-2), -1
assert_equal fib(-3), 2
assert_equal fib(-4), -3
assert_equal fib(-5), 5
assert_equal fib(-6), -8
assert_equal fib(-7), 13
assert_equal fib(-8), -21
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment