I think the method given by Paul is practical. the precise expression of F(n) is F(n) = K * (x1^n - x2^n ) where K = 1/sqrt(5), x1 = (1+sqrt(5))/2 and x2 = (1-sqrt(5))/2 because the x2 is small (about -0.61803...), the bigger n is ,the smaller the x2^n is. so, we consider K*(x1^2) is similar to F(n), according to the mathematic expression, you just get the result quickly. :) (this had been mentioned in <<The Art of Computer Programming>>, Volume1:Page82)
On 1月24日, 上午7时22分, "Paul Hsieh" <[EMAIL PROTECTED]> wrote: > On Jan 20, 6:56 am, "Manish Garg" <[EMAIL PROTECTED]> wrote: > > > i have one algo problem... > > > what can be the fastest way to find the two fibonacci numbers around x. > > say x is given to u then we have to find the two fibonacci numbers one is > > less then or equal to x and other one is greater then x. > > for exmple x =5 then output is 5 and 8..... > > f(n) = ceil (K*G^n), where K is some ratio that I don't remember (I > think its 1/sqrt(5) os something very similar to that) and G is the > golden ratio (1+sqrt(5))/2. Therefore, you can always take the number > x and calculate (ln(x) - ln(K))/ln(G), and that will be a good > approximation for n. You can then replug the integers surrounding that > calculation into f(n), and it should in fact be the two surrounding > fibonacci numbers. > > -- > Paul Hsiehhttp://www.pobox.com/~qed/http://bstring.sf.net/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
