While I like puzzles, I didn’t expect that I’d just be able to work this out, so I opened Google.
Good engineers don’t solve every problem themselves and don’t know everything, but they’re very good with Google searches.
It turns out that that there is a solution to fibonacci in terms of n which was discovered in the 1700s.
Source: http://www.
maths.
surrey.
ac.
uk/hosted-sites/R.
Knott/Fibonacci/fibFormula.
htmlI’m not going to get into the math or proving that this is accurate.
It’s complex, but that’s not really an issue, as going from O(n) complexity to O(c) (constant) complexity is worth a little extra time coding.
However, there is an issue with implementing this.
It uses some very large floating point (non-integer) numbers, and computers can struggle to do that math without having some rounding errors which could result in wrong answers.
While an engineer might be able to divine an accurate implementation and write thorough enough tests to be confident of that solution, it wouldn’t be worth it unless O(c) Fibonacci results on very large Fibonacci numbers was integral to a product.
It was cool to learn that the Fibonacci series can be defined like the power series generally is, however it’s not nearly as simple, and that is why most people aren’t aware of this definition.
There was a solution on that website that caught my eye though for its simplicity and complexity improvement.
There is a solution where fib(n) is effectively defined by fib(n/2) and fib(n/2 – 1), so it works strictly with integers, and reduces complexity to O(log n), which should be a huge improvement.
Source: http://www.
maths.
surrey.
ac.
uk/hosted-sites/R.
Knott/Fibonacci/fibFormula.
html#section3The above can be put in terms of F(n) by thinking of the top formula as a solution for odd values of n and the bottom as a solution for even values of n.
And since F(n) and F(n-1) produce both F(2n) and F(2n-1), the complexity of the solution can be reduced further by re-using the lower results either by calculating what indices are needed and then doing this iteratively, or by storing the values already computed in a recursive solution.
But for the sake of time, I just decided to implement the simplest recursive solution to see how it compared.
def fibr3(n): if n in (0,1): return n # if n is even if n % 2 == 0: a = n/2 b = n/2 – 1 fa = fibr3(a) fb = fibr3(b) return fa * (fa + 2 * fb) else: #n is odd a = (n + 1)/2 b = (n + 1)/2 – 1 fa = fibr3(a) fb = fibr3(b) return fa * fa + fb * fbThis new implementation, fibr3(n), computed the millionth Fibonacci number in under 2 seconds (as compared to ~10 seconds for the iterative solution).
Furthermore, it can compute more than the 30 millionth Fibonacci number before exhausting its Coderpad cpu threshold, whereas the iterative solution couldn’t reach 2 million.
The 30-millionth Fibonacci number has 6,269,629 digits by the way.
The simple output of program run-time from Coderpad interested me enough to perform a fun experiment with the Fibonacci series.
Unexpected results led me to a re-exploration of the power series, and a deeper investigation of the Fibonacci series.
In the end, I learned a lot more than I expected to when I started out and was inspired to share that journey, and perhaps a little lesson on Big-O complexity.
.