Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6.
My current approach: Find nth term (in decimal) in Fibonacci sequence using matrix exponentiation method and then convert the nth term to binary and then find number of 1's.
My question: Can this program be improved if I straight-away work with binary numbers? Is there a comparatively faster way to find nth term in Fibonacci sequence if we deal with binary numbers?
Fibonacci sequence in decimal: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Fibonacci sequence in binary: 1, 10, 11, 101, 1000, 1101, 10101, 100010, 110111, 1011001, ...
Best Answer
You would there would be a direct binary way to calculate this, but currently there is none discovered.
The fastest way is somewhere around $O(\log^2 n)$ where a binary way may look more like $O(\log n)$. This comparison is like the difference between how fast computers can add numbers, and how fast computers can multiply (multiplying use normal school-based, like we do. There are more complex ways that are much faster). So essentially the following way is still pretty fast compared to a direct approach:
Interestingly enough, instead of using $F_n$ in a binary way, the following algorithm uses $n$ in binary.
Take note of these basic properties of Fibonacci numbers:
With these properties we can double the position of a Fibonacci number's index, instead of going one by one, which makes it so much faster.
Steps:
Example:
Optimizations: