COMPUTING THE nth FIBONACCI

           COMPUTING THE nth FIBONACCI NUMBER

PROBLEM:

                Given a number n generate the nth member of the Fibonacci sequence.

 

AIM:

       To generate the nth Fibonacci number.

 

PROGRAM DESCRIPTION:

                

 

                                        F1=-1

                            F2=1

     -1 value is used in Fibonacci series.

                            F3=f1+f2;         →1

                            F1=f2;

                            F2=f3;

       From equ1 converting equ1 to general form,

                            F3→fn (generalized form)

                            F1→f3-f2

       Since f3 is repeated in terms of fn.

                            F2→f3-1→fn-1

       Therefore final solution of fn=fn-1+fn-2;

 

 

Fibonacci:  0 1 1 2 3 5 8 13 21 24

Index      :  1  2  3  4  5  6  7   8    9   10

 

 

Example:

            

                          F4=2

                          F5=3

        It is possible to get the next element.

                          F6=f4+f5      →2

        It is possible to get f7 from f5 and f6.

                          F7=f6+f5      →3

       From equ3 substitute f7=[f4+f5]+f5    →4

                          F8=f7+f6      →5

       From equ2 substitute

                          F6=f4+f5

       From equ4 substitute

                          F7=[f4+f5]+f5

       Here, the result can be stored in equ5.

                          F8=[(f4+f5)+f5]+[f4+f5]

                          F8=3f5+2f4

       Here, the equ starts from f4 and by doubling, then                                            stop at f8.

 

                          F8=3*3+2*2

                          F8=13;

       From this find the f2n value.

                                  

                          F8=f5²+f4²

       

        Now in generalised form

                          F2n=fn+1²+fn²

                          F2n=fnp1

                                      ↓

                                   f2n=fnp1*fnp1

                                             +

                                           fn*fn

        based on proof by induction,

                           f2n+1=2+fn+fn+1+fn+1²

                           f2np1=2*fn*fn+1+fn+1*fnp1;

 

 

ALGORITHM DESCRIPTION:

• Initialize n, then indicating the nth Fibonacci number is to be required.

              

• Derive the binary representation of n

                   by repeated division by 2 and store the

                   current element in array d[1.....i-1].

           

• Initialize the first two members of the doubling sequence.

                  

• Step by step from (p-1) th most significant digit in the binary representation of n to 1.

 

• Then use present set of Fibonacci number. To generate the set f2n and f2n+1.
• If the present binary digit d[k] is zero, then make the reassignment to fn and fn+1.
• Else extend the sequence by 1 number and then make the reassignment to fn and fn+1.

 

• The first Fibonacci numbers are

      

0. 1  1  2  3  5  8  13  21  24

 

IMPLEMENTATION:

               

                 #include<stdio.h>

                     #include<conio.h>

                     void main( )

                     {

                       int n,i=0;

                       while(n>1)

                    {

                       i=i+1;

                      if odd(n) then

                      d[i]=1;

                      else

                       d[i]=0;

                       n=n/2;

                     }

                      for(k=i-1;k≤1;k--)

                    {

                       sq fnp1=fnp1*fnp1;

                             f2n=fn*fn+sq fnp1;

                       f2np1=2*fn*fnp1+sq fnp1;

                       if d[k]=0

                    {

                       fn=f2n;

                       fnp1=f2np1;

                    }

                      else

                     {

                       fn=f2np1;

                       fnp1=f2np1+f2n;

                  }

                  }

 

APPLICATION:

               It is used in computation methods.

                 It is used to find the Fibonacci series.