Explain Fibonacci code

Question

#include<stdio.h>
#define max 2000

int arr1[max], arr2[max], arr3[max];

void fib();

int main()
{
    int num, i, j, flag = 0;

    for(i = 0; i<max; i++)
        arr1[i] = arr2[i] = arr3[i] = 0;

    arr2[max - 1] = 1;

    printf("Enter the term  : ");
    scanf("%d", &num);

    for(i = 0; i<num; i++)
    {
        fib();

        if(i == num - 3)
            break;

        for(j = 0; j<max; j++)
            arr1[j] = arr2[j];

        for(j = 0; j<max; j++)
            arr2[j] = arr3[j];

    }

    for(i = 0; i<max; i++)
    {
        if(flag || arr3[i])
        {
            flag = 1;
            printf("%d", arr3[i]);
        }
    }


    getch();
    return 1;
}

void fib()
{
    int i, temp;
    for(i = 0; i<max; i++)
        arr3[i] = arr1[i] + arr2[i];

    for(i = max - 1; i>0; i--)
    {
        if(arr3[i]>9)
        {
            temp = arr3[i];
            arr3[i] %= 10;
            arr3[i - 1] += (temp / 10);
        }
    }
}

The above code generates the nth Fibonacci number. I am not able to understand how this works. Basically the Fibonacci number get stored in a very large array arr3[].

Please explain the logic involved in this code.

How does the fib() function work as well?

Answer 1

The example code in the original post is dealing with large numbers by storing 1 decimal digit per element in each of the arrays. It initializes arr[3] = arr2[] = arr1[] = 0, then arr2[] = 1. In the loop, fib() performs one instance of arr3[] = arr1[] + arr2[], handling the carries, then the loop does arr[1] = arr2[], arr2[] = arr3[]. If num < 3, the for loop exits on the loop condition i < num, if n >= 3, the loop exit when i == (num-3). (This could be avoided). The print loop skips leading zeroes in arr3[], setting flag once a non-zero value is found. The code needs some minor fixes. Here is a fixed example. Note that getch() may be _getch() in some environments (from conio.h). The second example below only uses two arrays. Fibonacci numbers starting from 0 are 0 1 1 2 3 5 8 ...

#include <conio.h>
#include <stdio.h>
#define max 2000

int arr1[max], arr2[max], arr3[max];

void fib();

int main()
{
    int num, i, j;
    for(i = 0; i<max; i++)
        arr1[i] = arr2[i] = arr3[i] = 0;
    arr1[max - 1] = 1;

    printf("Enter the term  : ");
    scanf("%d", &num);

    for(i = 0; i<num; i++)
    {
        fib();
        for(j = 0; j<max; j++)
            arr1[j] = arr2[j];
        for(j = 0; j<max; j++)
            arr2[j] = arr3[j];
    }

    for(i = 0; i < max-1; i++)
        if(arr3[i])
            break;
    for( ; i < max; i++)
        printf("%d", arr3[i]);

    getch();
    return 0;
}

void fib()
{
    int i, temp;
    for(i = 0; i<max; i++)
        arr3[i] = arr1[i] + arr2[i];

    for(i = max - 1; i>0; i--)
    {
        if(arr3[i]>9)
        {
            temp = arr3[i];
            arr3[i] %= 10;
            arr3[i - 1] += (temp / 10);
        }
    }
}

This example only uses two arrays, by alternating which array contains the sum (a1 += a0, a0 += a1). It uses Duff's device to enter the loop. Since the largest sum from digit + digit + carry is < 20, the carry loop in fib() was simplified.

#include <conio.h>
#include <stdio.h>
#define max 2000

void fib(unsigned char *a0, unsigned char *a1);

int main()
{
unsigned char a0[max], a1[max];

    size_t i;
    int n;
    printf("Enter the term  : ");
    scanf("%d", &n);
    for(i = 0; i < max; i++)
        a0[i] = a1[i] = 0;
    a0[max-1] = n & 1;          /* if n even, a0=0=fib(0), a1=1=fib(-1) */
    a1[max-1] = 1 - a0[max-1];  /* if n odd,  a1=0=fib(0), a0=1=fib(-1) */
    switch(n&1){
        do{
            fib(a0, a1);
          case 1:
            fib(a1, a0);
          case 0:
            continue;
        }while(0 <= (n -= 2));
    }
    for(i = 0; i < max-1; i++)
        if(a0[i])break;
    for( ; i < max; i++)
        printf("%d", a0[i]);
    getch();
    return 0;
}

void fib(unsigned char *a0, unsigned char *a1)
{
    size_t i;
    for(i = 0; i < max; i++)
        a1[i] += a0[i];
    for(i = max - 1; i > 0; i--){
        if(a1[i] >= 10){
            a1[i]   -= 10;
            a1[i-1] += 1;
        }
    }
}

Answer 2

Here is a simple Fibonacci loop.

#include <stdio.h>

int main()
{
    int term = 20, last2=0, last1=1, fib, i;
    for (i=0; i<term; i++) {
        fib = last2 + last1;
        last2 = last1;
        last1 = fib;
    }
    printf ("Term %d = %d\n", i, fib);
    return 0;
}

Program output:

Term 20 = 10946

Although there is more than one idea as to where the sequence starts.

Answer 3

Here's a much better implementation of the Fibonacci series

#include<iostream>

using namespace std;

 main()
 {
    int n, c, first = 0, second = 1, next;

    cout << "Enter the number of terms of Fibonacci series you want" << endl;
    cin >> n;

    cout << "First " << n << " terms of Fibonacci series are :- " << endl;

    for ( c = 0 ; c < n ; c++ )
    {
       if ( c <= 1 )
       next = c;
       else
       {
          next = first + second;
          first = second;
          second = next;
       }
       cout << next << endl;
    }

    return 0;
 }