3
\$\begingroup\$

I've been learning more programming in the past few years (C, Java, Arduino) for my hobbies. I read the "C for Dummies" book and found that it was good, but did not cover much - especially pointers... One of my friends from college (CS major) suggested a simple program exercise to see if I could figure out how to use pointers. Well, I had to refer to a pdf of Ritchie's text "The C Programming Language" to learn about pointers. He asked me to make a program that returns the Fibonacci sequence. A month or so ago, I sent him my program, but he hasn't had time to review it since he is very busy with work these days. Basically what I am wondering about my program is if it is redundant or "too verbose" - basically is it written efficiently? IMO, as a hobbyist programmer, it works just fine.

Below is the source code file he initially sent to me:

/**

* @file  fibonacci.cpp
*
* @brief Prints out a partial Fibonacci sequence.

*/

#include <stdio.h>

// Function prototype for fibonacci()
unsigned int Fibonacci(unsigned int);

int main(int argc, char** argv)
{
    printf("Fibonacci Sequence:\n");

    for (unsigned int n = 0; n < 10; ++n)
    {
        unsigned int fib = Fibonacci(n);
        printf("%d ", fib);
    }

    return 0;
}

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int N)
{
    // Actual implementation goes here!!
}

Below is my version of the program that I sent to him for review:

/**

* @file  fibonacci.cpp
*
* @brief Prints out a partial Fibonacci sequence.

*/

#include <stdio.h>
unsigned int n;
char nMax[3];  //user input for sequence up to and including value @ this index
int Nmax;

// Function prototype for fibonacci()
unsigned int Fibonacci(unsigned int);

int main(int argc, char** argv)
{
    printf("Please input the Nth index of the last sequence value.\n");
    printf("Program will return entire Fibonacci Sequence up to and including Nth value.\n");

    gets(nMax);
    Nmax =atoi(nMax);

    for (n = 0; n < Nmax; ++n)
    {
        unsigned int fib = Fibonacci(n);
        printf("%d ", fib);
    }

    return 0;
}

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int n)
{
    // Actual implementation goes here!!

    unsigned int N;  //function output value

    //declare a temp array of sequence values
    unsigned int tempseq[100];

    // declare two ptrs
    unsigned int *prev;  //pointer to previous or (n-1) value in sequence
    unsigned int *prevprev;  //pointer to previous previous or (n-2) value in sequence

    if (n==0)
    {   N = 1;  //1st seed value
        tempseq[n] = N;     
    }   
    else if(n==1)
    {
        N = 1;  //2nd seed value
        tempseq[n] = N;         
    }
    else
    {   
        prev = &tempseq[n-1];        //prev ptr points to n-1 array element
        prevprev = &tempseq[n-2];    //prevprev ptr points to n-2 array element

        N = *prev + *prevprev;       //fibonacci recurrence relation
        tempseq[n] = N;              //add current value of N to the temp array 

    }   

    return N;

}

EDIT: Not to step on the toes of JS1 who recently replied, but I wanted to add an image here of my cmd line execution of my fibonacci.exe program to show that at least on my pc, it seems to work....

enter image description here

\$\endgroup\$
  • \$\begingroup\$ You could just use the closed form. \$\endgroup\$ – Barry Carter Mar 28 '16 at 19:38
  • \$\begingroup\$ @BarryCarter What do you mean by 'closed form' ? \$\endgroup\$ – PhilosophStein Mar 29 '16 at 14:09
  • \$\begingroup\$ en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression (sorry, meant to include that earlier). See also the section immediately following the section I linked. \$\endgroup\$ – Barry Carter Mar 29 '16 at 14:29
  • \$\begingroup\$ @BarryCarter Thanks for the link, I will look at it soon. Do you have any ideas why my code did not work for JS1 (who posted an answer below), but it does 'work' for me when I run my program in the windows cmd line? I did not fully read through JS1's answer yet because I feel it is important to first understand why my program apparently works for me... \$\endgroup\$ – PhilosophStein Mar 29 '16 at 15:07
  • \$\begingroup\$ The unsigned ints make me curious, but I don't think they should cause a problem. \$\endgroup\$ – Barry Carter Mar 29 '16 at 18:04
3
\$\begingroup\$

Doesn't work

The program doesn't work for me. Example:

$ ./fibonacci
Please input the Nth index of the last sequence value.
Program will return entire Fibonacci Sequence up to and including Nth value.
10
1 1 2 3 1 0 1 1 2 3

The problem is that the array tempseq is a temporary local variable, which means that every time you call the function Fibonacci(), that variable becomes unitialized. Your code is doing two things wrong:

  1. It assumes that tempseq will contain the values that it had from previous invocations of the function Fibonacci().
  2. It assumes that Fibonacci() will be called in a loop from 0 to n. If you just called Fibonacci(10) directly, it would not work because it depends on the answers for 8 and 9 being precomputed.

Fixes

  • To fix problem #1, you can declare your tempseq array using the static keyword. This makes the array persist across invocations. You can think of it like if the static keyword made the tempseq variable into a global variable.

  • To fix problem #2, you should not assume that an entry in tempseq is necessarily valid. You can do something like check if the entry is 0. If it is zero, then the entry must be computed, otherwise it is valid to use.

Rewrite

I have rewritten your function with the two problems fixed:

#define FIBMAX        100

// Computes the Nth Fibonacci number.
unsigned int Fibonacci(unsigned int n)
{
    // FibResult is a persistent array of already computed values.
    // We initialize fibResult[0] and [1] to take care of special cases.
    static unsigned int fibResult[FIBMAX] = { 1, 1 };

    // Guard against bad input.
    if (n >= FIBMAX)
        return 0;

    if (fibResult[n] == 0) {
        // We have not previously computed this entry, so compute it now
        // using the recurrence relation.
        //
        // Note: calling Fibonacci(n-1) guarantees that fibResult[n-2] will
        // be set, so we just use that to avoid one function call.  We
        // could have written this and it would have worked just fine:
        //
        // fibResult[n] = Fibonacci(n-1) + Fibonacci(n-2);
        //
        fibResult[n] = Fibonacci(n-1) + fibResult[n-2];
    }

    return fibResult[n];
}

This rewrite also:

  1. Replaces the magic number 100 with a defined constant and checks the input so that we don't have any buffer overflow problems.
  2. Takes care of the special cases of n=0 and n=1 by filling in those entries in the fibResult array.

Simpler way

You might also want to consider a simpler function that doesn't use an array of precomputed values. Calculating a fibonacci number can be done in a simple loop like this:

unsigned int Fibonacci(unsigned int n)
{
    unsigned int f1 = 1;
    unsigned int f2 = 1;

    for (unsigned int i = 0; i < n; i++) {
        f2 = f1 + f2;
        f1 = f2 - f1;
    }
    return f1;
}
\$\endgroup\$
  • \$\begingroup\$ The program may not work for you, but can you explain why it seemingly worked for me when I ran it from the windows cmd line? \$\endgroup\$ – PhilosophStein Mar 29 '16 at 14:10
  • 1
    \$\begingroup\$ @PhilosophStein Because whatever compiler you used placed the temporary array someplace on the stack where the call to printf() did not happen to clobber it. If you really want to know the answer, you'll need to understand where local variables are stored (on the stack), and how the stack works when you call into a function. \$\endgroup\$ – JS1 Mar 29 '16 at 17:36
  • \$\begingroup\$ At JS1 (since I cannot seem to be able to reply directly to your user name...): thanks for providing that explanation. I see that you did not even need to use pointers to accomplish the goal of the program! \$\endgroup\$ – PhilosophStein Apr 2 '16 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.