[Math] Finding the binary representation of the $n$th Fibonacci term

binarycontest-mathfibonacci-numbers

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:

  • $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:

  1. Convert the $n$ (as in $F_n$) to binary. Ex: The $11th$ Fibonacci number, so $11$ in binary is $1011_2$
  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$.
  3. Calculate $(F_{2k-1}, F_{2k},F_{2k+1})$ using the formulas listed above.
  4. 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.
  5. 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:

  1. To find $F_{13}$, $n = 13$ in binary is $1101_2$
  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)$
  3. Because the $2nd$ digit from the left is a $1$, we will use $(1,2)$ for our next values.
  4. Next values: $(5,8,13)$. $3rd$ digit from the left is a $0$ so we use (5,8).
  5. 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$.
Related Question