Pages

Wednesday, July 10, 2013

Fast Fibonacci

I was looking for a faster Fibonacci algorithm and stumbled across this one. The doubling method assumes we know F(n) and F(n+1) to produce F(2n) and F(2n+1) out of the following formulas:

F(2n) = F(n) * (2*F(n+1) - F(n))
F(2n+1) = F(n+1)2 + F(n)2


The formulas can be extracted from the matrix exponentiation algorithm mentioned in the above article and reduced of redundant calculations.




Note:
Integer.numberOfLeadingZeros is a Java shortcut to get to the highest set bit. It may be implemented in some other way in different languages. It is needed here to avoid a few iterations; in our case considering we have 32 iterations and we can get an n up to 92, we can save up to 24 iterations.

2 comments:

  1. Hi, I dint understood that how we are saving the number of iterations

    ReplyDelete
  2. While almost every day of the four-week period will be geared towards the World Cup in some way, there are seven dates that will hold greater significance. Australia’s match against Afghanistan on June 1 will end the intensive, 29-day preparation period and open the door to the nation’s highly-anticipated World Cup title defence.His heroics in the competition earned him a place in the national team and just before the Cricket World Cup 2019 Live, Shakib scored his maiden ODI hundred against Canada. Later he played a key role for Bangladesh as the Tigers outclassed teams like India and South Africa in the World Cup in Caribbean. Following that exposure, Shakib never looked back. They beat a depleted hosts. In the 2011 World Cup at home, he led the Bangladesh team but failed to live up to the expectations. And later that year, he was stripped off the captaincy.

    ReplyDelete