Tutorialspoint.dev

Find Index of given fibonacci number in constant time

We are given a Fibonacci number. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …..
We have to find index of given Fibonacci number, i.e. like fibonacci number 8 is at index 6.

Examples :

Input : 13
Output : 7

Input : 34
Output : 9



Method 1 (Simple)
Simple approach is to find Fibonacci numbers up to given Fibonacci number and count number of iteration performed.

C++

// A simple C++ program to find index of given
// Fibonacci number.
#include<bits/stdc++.h>
  
int findIndex(int n)
{
    // if Fibonacci number is less than 2,
    // its index will be same as number
    if (n <= 1)
        return n;
  
    int a = 0, b = 1, c = 1;
    int res = 1;
  
    // iterate until generated fibonacci number 
    // is less than given fibonacci number
    while (c < n)
    {
        c = a + b;
          
        // res keeps track of number of generated 
        // fibonacci number
  
        res++;
        a = b;
        b = c;
    }
    return res;
}
  
// Driver program to test above function
int main()
{
    int result = findIndex(21);
    printf("%d ", result);
}
  
// This code is contributed by Saket Kumar

Java

// A simple Java program to find index of 
// given Fibonacci number.
import java.io.*;
  
class GFG {
      
    static int findIndex(int n)
    {
          
        // if Fibonacci number is less 
        // than 2, its index will be
        // same as number
        if (n <= 1)
            return n;
      
        int a = 0, b = 1, c = 1;
        int res = 1;
      
        // iterate until generated fibonacci
        // number is less than given 
        // fibonacci number
        while (c < n)
        {
            c = a + b;
              
            // res keeps track of number of
            // generated fibonacci number
            res++;
            a = b;
            b = c;
        }
          
        return res;
    }
      
    // Driver program to test above function
    public static void main (String[] args) 
    {
        int result = findIndex(21);
        System.out.println( result);
    }
}
  
// This code is contributed by anuj_67.

C#

// A simple C# program to 
// find index of given 
// Fibonacci number.
using System;
class GFG 
{
    static int findIndex(int n)
    {
          
        // if Fibonacci number 
        // is less than 2, its 
        // index will be same 
        // as number
        if (n <= 1)
            return n;
      
        int a = 0, b = 1, c = 1;
        int res = 1;
      
        // iterate until generated 
        // fibonacci number is less 
        // than given fibonacci number
        while (c < n)
        {
            c = a + b;
              
            // res keeps track of 
            // number of generated
            // fibonacci number
            res++;
            a = b;
            b = c;
        }
          
        return res;
    }
      
    // Driver Code
    public static void Main () 
    {
        int result = findIndex(21);
        Console.WriteLine(result);
    }
}
  
// This code is contributed
// by anuj_67.

/div>

Python3

# A simple Python 3 program to find 
# index of given Fibonacci number.
  
def findIndex(n) :
      
    # if Fibonacci number is less than 2,
    # its index will be same as number
    if (n <= 1) :
        return n
   
    a = 0
    b = 1
    c = 1
    res = 1
   
    # iterate until generated fibonacci number 
    # is less than given fibonacci number
    while (c < n) :
        c = a + b
           
        # res keeps track of number of  
        # generated fibonacci number
        res = res + 1
        a = b
        b = c
          
    return res
  
# Driver program to test above function
result = findIndex(21)
print(result)
  
# this code is contributed by Nikita Tiwari

PHP

<?php
// A simple PHP program to 
// find index of given
// Fibonacci number.
  
function findIndex($n)
{
      
    // if Fibonacci number
    // is less than 2,
    // its index will be 
    // same as number
    if ($n <= 1)
        return $n;
  
    $a = 0; $b = 1; $c = 1;
    $res = 1;
  
    // iterate until generated 
    // fibonacci number 
    // is less than given
    // fibonacci number
    while ($c < $n)
    {
        $c = $a + $b;
          
        // res keeps track of 
        // number of generated 
        // fibonacci number
  
        $res++;
        $a = $b;
        $b = $c;
    }
    return $res;
}
  
// Driver Code
$result = findIndex(21);
echo($result);
  
// This code is contributed by Ajit.
?>


Output:

 8

 

Method 2 (Formula based)

But here, we needed to generate all the fibonacci number up to provided fibonacci number. But, there is quick solution for this problem. Let’s see how !

Note that computing log of a number is O(1) operation in most of the platforms [Source : Stackoverflow]

Fibonacci number is described as,
Fn = 1 / sqrt(5) (pow(a,n) – pow(b,n)) where
a = 1 / 2 ( 1 + sqrt(5) ) and b = 1 / 2 ( 1 – sqrt(5) )

On neglecting pow(b, n) which is very small for large value of n, we get
n = round { 2.078087 * log(Fn) + 1.672276 }
where round means round to nearest integer.

Below is the implementation of above idea.

C++

// C++ program to find index of given Fibonacci
// nunber
#include<bits/stdc++.h>
  
int findIndex(int n)
{
    float fibo = 2.078087 * log(n) + 1.672276;
  
    // returning rounded off value of index
    return round(fibo);
}
  
// Driver program to test above function
int main()
{
    int n = 55;
    printf("%d ", findIndex(n));
}

Java

// A simple Java program to find index of given
// Fibonacci number
public class Fibonacci
{
  
  static int findIndex(int n)
  {
    float fibo = 2.078087F * (float) Math.log(n) + 1.672276F;
  
    // returning rounded off value of index
    return Math.round(fibo);
  }
  
  public static void main(String[] args)
  {
    int result = findIndex(55);
    System.out.println(result);
  }
}

Python

# Python 3 program to find index of given Fibonacci
# nunber
  
import math
def findIndex(n) :
    fibo = 2.078087 * math.log(n) + 1.672276
   
    # returning rounded off value of index
    return round(fibo)
  
  
# Driver program to test above function
n = 21
print(findIndex(n))
  
  
# This code is contributed by Nikita Tiwari.

C#

// A simple C# program to find 
// index of given Fibonacci number
using System;
  
class Fibonacci {
  
static int findIndex(int n)
{
    float fibo = 2.078087F * (float) Math.Log(n) +
                                        1.672276F;
  
    // returning rounded off value of index
    return (int)(Math.Round(fibo));
}
  
  // Driver code
  public static void Main()
  {
    int result = findIndex(55);
    Console.Write(result);
  }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// PHP program to find index
// of given Fibonacci Number
  
function findIndex($n)
{
    $fibo = 2.078087 * log($n) + 1.672276;
  
    // returning rounded off
    // value of index
    return round($fibo);
}
  
// Driver code
$n = 55;
echo(findIndex($n));
  
// This code is contributed by Ajit.
?>


Output:

 10

Reference :
https://math.stackexchange.com/questions/848691/how-to-tell-if-a-fibonacci-number-has-an-even-or-odd-index

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter