3 Replies - 3098 Views - Last Post: 17 April 2012 - 07:23 PM

#1 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12616
  • View blog
  • Posts: 45,771
  • Joined: 27-December 08

Fibonacci Numbers in O(1) Time

Posted 05 June 2011 - 11:01 AM

Description: This solution generates the nth Fibonacci number through solving the linear recurrence. The solution is:
F(n) = (sqrt(5)/5)((1+sqrt(5))/2)^n - (sqrt(5)/5)((1-sqrt(5))/2)^n
public int fib(int n){
    double x = Math.sqrt(5)/5;
    
    double termOne = x * Math.pow((1+sqrt(5))/2, n);
    double termTwo = -x * Math.pow((1-sqrt(5))/2, n);
 
    return (int)(termOne + termTwo);
}

Is This A Good Question/Topic? 0
  • +

Replies To: Fibonacci Numbers in O(1) Time

#2 ahamedirshad123   User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 15-March 10

Re: Fibonacci Numbers in O(1) Time

Posted 23 June 2011 - 04:42 AM

Wow, This code saves lot of time. This function should return double instead of int,no?
Was This Post Helpful? 0
  • +
  • -

#3 Mobuis1995   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 15-February 12

Re: Fibonacci Numbers in O(1) Time

Posted 17 April 2012 - 07:15 PM

Wow, very cool. May I ask about your thought-process? I have no idea how you came up with this, especially the (square root of five) / 5
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12616
  • View blog
  • Posts: 45,771
  • Joined: 27-December 08

Re: Fibonacci Numbers in O(1) Time

Posted 17 April 2012 - 07:23 PM

It's actually taught in Discrete Math courses. You can solve linear, homogenous recurrences like linear, homogenous differential equations.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1