11 ms·

The rigth way to do fibonacci would probably be to add memoization...

by khebbie 8y ago

khebbie 8y ago
But I suppose not adding memoization will reveal the real performance of the language
- khebbie 8y ago
  Just not idiomatic code
Al-Khwarizmi 8y ago
The "right" way to do Fibonacci is to use matrix multiplication to get the nth Fibonacci number in logarithmic time (google Fibonacci log n matrix).
- braythwayt 8y ago
  A matrix implementatiom in JavaScript: http://raganwald.com/2015/12/20/an-es6-program-to-compute-fibonacci.html http://raganwald.com/2015/12/20/an-es6-program-to-compute-fi... It is based on a Ruby implementation: http://raganwald.com/2008/12/12/fibonacci.html http://raganwald.com/2008/12/12/fibonacci.html
toolslive 8y ago
Why not calculate it in constant time ? https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula https://artofproblemsolving.com/wiki/index.php?title=Binet%2...
- edflsafoiewq 8y ago
  You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out. Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
  - toolslive 8y ago
    true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)
- braythwayt 8y ago
  As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory: http://raganwald.com/2013/03/26/the-interview.html http://raganwald.com/2013/03/26/the-interview.html
spatulon 8y ago
Or turn it into a simple iterative process, instead of a recursive process. They explain how quite simply in SICP: http://sarabander.github.io/sicp/html/1_002e2.xhtml http://sarabander.github.io/sicp/html/1_002e2.xhtml (Ctrl-F "We can also formulate an iterative process for computing the Fibonacci numbers.") Here's a Python implementation: def fib(n): a = 1 b = 0 i = 0 while i < n: temp = a a += b b = temp i += 1 return a With that, fib(100000) takes half a second to compute on my machine.

The rigth way to do fibonacci would probably be to add memoization...

khebbie 8y ago

But I suppose not adding memoization will reveal the real performance of the language

khebbie 8y ago
Just not idiomatic code

Al-Khwarizmi 8y ago

The "right" way to do Fibonacci is to use matrix multiplication to get the nth Fibonacci number in logarithmic time (google Fibonacci log n matrix).

braythwayt 8y ago
A matrix implementatiom in JavaScript: http://raganwald.com/2015/12/20/an-es6-program-to-compute-fibonacci.html http://raganwald.com/2015/12/20/an-es6-program-to-compute-fi... It is based on a Ruby implementation: http://raganwald.com/2008/12/12/fibonacci.html http://raganwald.com/2008/12/12/fibonacci.html

toolslive 8y ago

Why not calculate it in constant time ? https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula https://artofproblemsolving.com/wiki/index.php?title=Binet%2...

edflsafoiewq 8y ago
You can't really compute it in constant time since the number of bits in the nth Fibonacci number is O(n), so you need to take at least that long just to write the result out. Computing with Binet's formula is also rather tricky. You just need to round φ^n/√5, but how many bits of √5 do you need to use?
- toolslive 8y ago
  true: adding 2 64 bit numbers is constant time for me, but adding 2 4096 bit numbers is not. Eventually, even the simplest operation becomes O(ln n)
braythwayt 8y ago
As mentioned in other comments, working with floating point numbers in practice is trickier than it looks in theory: http://raganwald.com/2013/03/26/the-interview.html http://raganwald.com/2013/03/26/the-interview.html

spatulon 8y ago

Or turn it into a simple iterative process, instead of a recursive process. They explain how quite simply in SICP: http://sarabander.github.io/sicp/html/1_002e2.xhtml http://sarabander.github.io/sicp/html/1_002e2.xhtml (Ctrl-F "We can also formulate an iterative process for computing the Fibonacci numbers.") Here's a Python implementation: def fib(n): a = 1 b = 0 i = 0 while i < n: temp = a a += b b = temp i += 1 return a With that, fib(100000) takes half a second to compute on my machine.