CODEWITHSUNDEEP
fibonacciseries
Nasif Imtiaz Ohi
Nasif Imtiaz Ohi

Reputation: 1713

if input is nth term in fibonacci series, finding n

in fibonacci series let's assume nth fibonacci term is T. F(n)=T. but i want to write a a program that will take T as input and return n that means which term is it in the series( taken that T always will be a fibonacci number. )i want to find if there lies an efficient way to find it.

Upvotes: 0

Views: 1376

Answers (2)

user1679215
user1679215

Reputation: 11

The first step is to implement fib numbers in a non-recursive way such as

fib1=0;fib2=1;
for(i=startIndex;i<stopIndex;i++)
{
     if(fib1<fib2)
     {
        fib1+=fib2;
        if(fib1=T) return i;
        if(fib1>T) return -1;
     }
     else
     {
        fib2+=fib1;
        if(fib2=T) return i;
        if(fib2>t) return -1;
     }
}

Here startIndex would be set to 3 stopIndex would be set to 10000 or so. To cut down in the iteration, you can also select 2 seed number that are sequential fib numbers further down the sequence. startIndex is then set to the next index and do the computation with an appropriate adjustment to the stopIndex. I would suggest breaking the sequence up in several section depending on machine performance and the maximum expected input to minimize the run time.

Upvotes: 0

Gaminic
Gaminic

Reputation: 581

The easy way would be to simply start generating Fibonacci numbers until F(i) == T, which has a complexity of O(T) if implemented correctly (read: not recursively). This method also allows you to make sure T is a valid Fibonacci number.

If T is guaranteed to be a valid Fibonacci number, you can use approximation rules: Formula

It looks complicated, but it's not. The point is: from a certain point on, the ratio of F(i+1)/F(i) becomes a constant value. Since we're not generating Fibonacci Numbers but are merely finding the "index", we can drop most of it and just realize the following:

breakpoint := f(T)
Any f(i) where i > T = f(i-1)*Ratio = f(T) * Ratio^(i-T)

We can get the reverse by simply taking Log(N, R), R being Ratio. By adjusting for the inaccuracy for early numbers, we don't even have to select a breakpoint (if you do: it's ~ correct for i > 17).

The Ratio is, approximately, 1.618034. Taking the log(1.618034) of 6765 (= F(20)), we get a value of 18.3277. The accuracy remains the same for any higher Fibonacci numbers, so simply rounding down and adding 2 gives us the exact Fibonacci "rank" (provided that F(1) = F(2) = 1).

Upvotes: 2

Related Questions