fibonacci
Can a Fibonacci function be written to execute in O(1) time?
Here is a near O(1) solution for a Fibonacci sequence term. Admittedly, O(log n) depending on the system Math.pow() implementation, but it is Fibonacci w/o a visible loop, if your interviewer is looking for that. The ceil() was due to rounding precision on larger values returning .9 repeating. Example in JS: function fib (n) { … Read more
Understanding a recursively defined list (fibs in terms of zipWith)
I’ll give a bit of an explanation of how it works internally. First, you must realise that Haskell uses a thing called a thunk for its values. A thunk is basically a value that has not yet been computed yet — think of it as a function of 0 arguments. Whenever Haskell wants to, it … Read more
Ruby Fibonacci algorithm
Naive fibonacci makes a lot of repeat calculations – in fib(14) fib(4) is calculated many times. You can add memoization to your algorithm to make it a lot faster: def fib(n, memo = {}) if n == 0 || n == 1 return n end memo[n] ||= fib(n-1, memo) + fib(n-2, memo) end fib 14 … Read more
What is the fastest way to write Fibonacci function in Scala?
The fastest versions are the ones that deviate from the usual addition scheme in some way. Very fast is the calculation somehow similar to a fast binary exponentiation based on these formulas: F(2n-1) = F(n)² + F(n-1)² F(2n) = (2F(n-1) + F(n))*F(n) Here is some code using it: def fib(n:Int):BigInt = { def fibs(n:Int):(BigInt,BigInt) = … Read more
Fibonacci sequence in Ruby (recursion)
Try this def fibonacci( n ) return n if ( 0..1 ).include? n ( fibonacci( n – 1 ) + fibonacci( n – 2 ) ) end puts fibonacci( 5 ) # => 5 check this post too Fibonacci One-Liner and more .. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby) You have now been bombarded with many solutions 🙂 regarding problem … Read more
An inverse Fibonacci algorithm?
Since OP has asked about matrix solution not involving any floating point computations, here it is. We can achieve O(logn) complexity this way, assuming numeric operations have O(1) complexity. Let’s take 2×2 matrix A having following structure 1 1 1 0 Now consider vector (8, 5), storing two consecutive fibonacci numbers. If you multiply it … Read more
Test if a number is fibonacci
A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion. Hope this helps
How does the fibonacci recursive function “work”?
You’re defining a function in terms of itself. In general, fibonnaci(n) = fibonnaci(n – 2) + fibonnaci(n – 1). We’re just representing this relationship in code. So, for fibonnaci(7) we can observe: fibonacci(7) is equal to fibonacci(6) + fibonacci(5) fibonacci(6) is equal to fibonacci(5) + fibonacci(4) fibonacci(5) is equal to fibonacci(4) + fibonacci(3) fibonacci(4) is … Read more
Recursive Fibonacci memoization
You need to distinguish between already calculated number and not calculated numbers in the dictionary, which you currently don’t: you always recalculate the numbers. if (n == 0) { // special case because fib(0) is 0 return dictionary[0]; } else { int f = dictionary[n]; if (f == 0) { // number wasn’t calculated yet. … Read more