This is a great solution since it is relatively simple and efficient, as it run in
O(n)
.
But, can we do better?
Yes we can!
The Brilliancy
This one is for the algo-holics and thanks to its simplicity and efficiency, I consider it to be a brilliant solution.
We are going to find the n'th Fibonacci number in
O(log(n))
!
Efficient Power Algorithm
For starters, let's see how we can calculate
xn
in an efficient time complexity of
O(log(n))
.
This algorithm is based on the fact that:
If
n
is
even
:
xn=xn/2∗xn/2
If
n
is
odd
:
xn=x(n−1)/2∗x(n−1)/2∗x
Since this is right for every
n>2
, we can claim that:
(Fn−2Fn−1)=(1101)(Fn−3Fn−2)
(Fn−3Fn−2)=(1101)(Fn−4Fn−3)
⋮
(F2F3)=(1101)(F1F2)=(1101)(11)=(12)
And now, let's put it all together:
(Fn−1Fn)=(1101)(Fn−2Fn−1)
(Fn−1Fn)=(1101)(1101)(Fn−3Fn−2)
(Fn−1Fn)=(1101)(1101)(1101)(Fn−4Fn−3)
⋮
(Fn−1Fn)=(1101)n−2(F1F2)
(Fn−1Fn)=(1101)n−2(11)
So now, we see that if we want to know the n'th Fibonacci number (and the one before), all we have to do is some matrix multiplication! More specifically, we need to raise a matrix to the power of
n−2
. But we already know how to calculate
pow(x,n)
in
O(log(n))
. This is amazingggg! Note that every matrix multiplication is
O(1)
.
So, suppose we adjust our power algorithm to work with matrix multiplication instead of regular multiplication, we can calculate
(1101)n−2
in
O(log(n))
, then multiply it by
(11)
and voilà! We calculated both
Fn
and
Fn−1
in
O(log(n))
!
Take a minute, let that sink in 😌.
Bonus
So, after you took a minute to chill out your ecstasy, think about it: Is Fibonacci special? Or this method going to work for all recursive equations like Fibonacci?
Well, while Fibonacci IS special, this method is going to work for all equations similar to Fibonacci. For example, let's define the Zigi sequence as follow:
Z1=7 Z2=−4 Zn=2∗Zn−1−3∗Zn−2
The secret is simple: Just find the correct matrix, and the magic will come. Here, we can see that:
(Zn−1Zn)=(120−3)(Zn−2Zn−1)
⋮
(Zn−1Zn)=(120−3)n−2(−47)
And, as you see, the n'th Zigi's number can be computed in
O(log(n))
.
Brilliant. I'm sending this to my grandfather and father who are both mathematicians. I expect they will talk about it at family gatherings for months...
Top comments (2)
Brilliant. I'm sending this to my grandfather and father who are both mathematicians. I expect they will talk about it at family gatherings for months...
That’s cool man! Glad to hear 😊