Skip to content

Instantly share code, notes, and snippets.

@dzautner

dzautner/fib.js

Created January 15, 2018 12:42
Show Gist options
  • Save dzautner/9409bf646a8a6e5e61b573b854c468f7 to your computer and use it in GitHub Desktop.
Save dzautner/9409bf646a8a6e5e61b573b854c468f7 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
fib.js
const fibonacciResults = {}
function Fibonacci(n) {
if (!fibonacciResults[n]) {
fibonacciResults[n] = n <= 1 ? 1 : Fibonacci(n - 1) + Fibonacci(n - 2);
}
return fibonacciResults[n];
}
@dzautner
Copy link
Author

constant complexity / O(1)

function fibonacci(n) {
 return Math.round(
 (Math.pow((1 + Math.sqrt(5)) / 2, n) — 
 Math.pow(-2 / (1 + Math.sqrt(5)), n)) / 
 Math.sqrt(5)
 );
}

@dzautner
Copy link
Author

a bit clearer

const goldenRatio = 1.6180339887498948482045868;

fib = n => Math.floor(Math.pow(goldenRatio, n) - Math.pow(( 1 - goldenRatio ), n) / Math.sqrt(5))

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