gr33n7007h/fdf.rb

Created July 20, 2020 03:46

Star () You must be signed in to star a gist
Fork () You must be signed in to fork a gist

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/gr33n7007h/73e90b357266a1a8f7e8b43350ba2afc.js"></script>
Save gr33n7007h/73e90b357266a1a8f7e8b43350ba2afc to your computer and use it in GitHub Desktop.

Download ZIP

Fast Doubling Fibonacci

Raw

fdf.rb

	def fdf(n)
	return 1 if n <= 2
	k = n >> 1
	a = fdf(k + 1)
	b = fdf(k)
	n % 2 == 1 ? (a * a + b * b) : (b * (2 * a - b))
	end

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment