Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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, ...
share|improve this question
    
Computers work in binary by default.... –  Hurkyl Feb 7 '13 at 10:08
    
I think you got me wrong! I am asking, whether there is a faster way if we use binary mathematics, like bit-shifting, etc? Or the binary sequence itself gives a pattern to find nth term quickly? –  stalin Feb 7 '13 at 10:11
    
The number of ones is tabulated at oeis.org/A011373 and code is given for Maple and Mathematica. –  Gerry Myerson Feb 7 '13 at 10:41
add comment

1 Answer 1

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$.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.