facebook like button

07 December, 2011

getting nth term of fibonacci series unlimited number of terms

The need:
     The program for fibonacci series is very simple but those programs give you terms upto the limit of integer size. This is a program to print Fibonacci series upto 10000th term. I wrote this program when I noticed people coming on previous fibonacci program in search of 2011th term or so.
The code: 
--------------------------------------------
#define MAX 2100 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
void print(char x[]); 
void add(char x[], char y[], char z[]); 

int main() 
{ 
    int i=0,j,num; 
    char n_minus1[MAX]="1",n_minus2[MAX]="1",nth[MAX]=""; 
    printf("This is a program to print fibonacci sequence upto desired term.(max 10000)\n"); 
    printf("\nenter a natural number upto which do you want fibonacci series\n");
    scanf("%d",&num); 
    if(    num<1||num>10000) 
    { 
        printf("The desired term index was either invalid or greater than 10000\n"); 
        exit(0); 
    }
    printf("\noptions:\n1. print only %dth term\n2. print all terms\n",num);
    scanf("%d",&j);
    switch(j)
    {
        case 1: 
                if(num<2){
                printf("The first term is 1\n");
                break;
                }
                if(num<3){
                printf("The second term is 1\n");
                break;
                }
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                printf("The %dth term is ",num);
                print(nth);
                break;
        case 2:    printf("\nFibonacci series upto %dth term\n\n",num);
                printf("term \tvalue\n",num);
                printf("%4d \t1\n",1);
                if(num<2)
                break;
                printf("%4d \t1\n",2);
                if(num<3)
                break;
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  printf("%4d\t",i+1);
                  print(nth);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                break;
        default: printf("Invalid choice...!!! \tExiting\n");
                exit(0);
    }
    printf("\n\nprgram finished successfully.\t press any key to continue\n");
    getchar(); 
    return 0; 
} 

void print(char x[]) 
{ 
    int i; 
    for(i=strlen(x)-1;i>=0;i--) 
    { 
        putchar(x[i]); 
        if(i%5==0) 
        putchar(' '); 
    } 
    putchar('\n'); 
    return; 
} 

void add(char x[],char y[],char z[]) 
{ 
    int i,ylen,zlen,equal;
    char c = 0,temp;
    ylen = strlen(y);
    zlen = strlen(z);
    equal = (ylen == zlen) ? 1 : 0; 
    for(i=0;i<zlen;i++) 
    { 
        x[i]=c + y[i] + z[i] - '0'; 
        if( x[i]-'0' > 9)
        {
            x[i]-=10;
            c=1;
        }
        else
        c=0; 
    }
    if(equal)
    {
        if(c!=0)
        {
            x[i]=c + '0';
            x[i+1]='\0';
        }
    }
    else
    {
        x[i]=c + y[i];
        x[i+1]='\0';
    } 
    return; 
}
-------------------------------------------- 

The approach: 
This program creates a Fibonacci series upto the terms given by the user. The logic is same. Just go with the definition of Fibonacci that any term is the sum of its two preceding terms. Here nth always hold current term and n_minus1 and n_minus2 hold previous 2 terms(except for first 2 terms case). I have already told that integers are very small to work when we have more than 10digits in the scene so these 3 variables are taken as strings. add() is UDF defined by me which takes 3 arguments x,y,z. add puts sum of y and z into x. This add() is the only twist here to differentiate this program from program38 of this blog.

Remarks:
1. In this program is capable to give you upto 10000th term of fibonacci easily.
2. You can get upto more terms. all you have to do is to increase the value of max in #define statement. This is why I wrote unlimited in the title.

No comments:

Post a Comment

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply