Finding the binary representation of the $n$th Fibonacci term 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, ...

 A: 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:


*

*$F_{2k+1} = 4F_k^2 - F_{k-1}^2 + 2(-1)^k$

*$F_{2k-1} = F_k^2 + F_{k-1}^2$

*$F_{2k} = F_{2k+1} - F_{2k-1}$


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:


*

*Convert the $n$ (as in $F_n$) to binary. Ex: The $11th$ Fibonacci number, so $11$ in binary is $1011_2$ 

*Have $F_0 = 0$ and $F_1 = 1$, and let $k = 1$ to start. Lastly start from the $2nd$ binary digit place from the left. In this case it is the $0$.

*Calculate $(F_{2k-1}, F_{2k},F_{2k+1})$ using the formulas listed above.

*If the digit place is $0$ use $(F_{2k-1}, F_{2k})$, if it is odd use $(F_{2k},F_{2k+1})$ for the next values you substitute for $(F_{k-1},F_k)$. Now shift the digit place one to the right.

*Repeat steps 3-4 until all the digits places are gone, and you will get your final Fibonacci number which will end up being whatever value you end up for your next $F_k$.


Example:


*

*To find $F_{13}$, $n = 13$ in binary is $1101_2$

*Starting from $(F_0,F_1) = (0,1)$, the next value sets are: $(1^2+0^2,F_{2k+1}-F_{2k-1},4(1)^2-0^2-2) = (1, 2-1, 2) = (1,1,2)$

*Because the $2nd$ digit from the left is a $1$, we will use $(1,2)$ for our next values.

*Next values: $(5,8,13)$. $3rd$ digit from the left is a $0$ so we use (5,8).

*Next values: $(89,144,233)$. $4th$ digit form the left is a $1$ so we use $(144,233)$, but that was the last digit place, so our answer is $F_k$, which is $233$.


Optimizations: 


*

*Calculate $F_k^2$ and $F_{k-1}^2$ first and recycle them when
calculating $F_{2k+1}$ and $F_{2k-1}$.

*Because $2(-1)^k$ is $-2$ when $k$ is odd, and $+2$ when $k$ is even, Whatever digit place read to determine what values to use for $(F_{k-1},F_k$), also predicts which $+2$ or $-2$ to use. So in our example because we read a $1$ in the $2nd$ place, we would use $-2$ for the next $2(-1)^k$. And because we read a $0$ in the $3rd$ place, we would use $+2$ for the $2(-1)^k$ after. So use a $+2$ if you read a $0$, and use $-2$ if you read a $1$.

