2
\$\begingroup\$

I'm trying out a new editor (CLion) and I decided to try an old well known programming problem. I also decided to try out C99 rather than C89.

This program calculates the nth term of the Fibonacci Sequence where the value of the current term is the sum of the 2 previous terms. The first 4 terms are 0, 1, 1, 2. The upper limit applied in the program is the 91st term, on my computer using long long the term value goes negative at 93rd term.

All Comments and observations are appreciated. I'm especially interested in performance, function and variable names and suggestions about how I can increase the range of terms using integers. I know I can use doubles but that may incur floating point errors at some point. As far as performance goes, the program has a nice small memory signature (0.5% of the system memory) speed is where I would be worried.

#include <stdio.h>
#include <stdlib.h>

static const int MinimumTerm = 0;
static const int MaximumTerm = 91;
static const int MaxTries = 3;
static const int inputFailure = -1;

static int getTermCount()
{
    char *fmtstr = "Please enter an integer value between %d and %d\n";
    printf(fmtstr, MinimumTerm, MaximumTerm);

    int term = 0;
    int count = 0;
    do
    {
        scanf("%d", &term);
        if (count < MaxTries)
        {
            if (term < MinimumTerm || term > MaximumTerm)
            {
                fprintf(stderr, fmtstr, MinimumTerm, MaximumTerm);
            }
        }
        else
        {
            return inputFailure;
        }
        count++;
    } while (term < MinimumTerm || term > MaximumTerm);

    return term;
}

static long long getNthFibonacciTerm(int term)
{
    int termCount = 2;
    long long prevValue = 0;
    long long nthValue = 1;

    switch  (term)
    {
        case 0: return 0;
        case 1: return 1;
    }

    while  (termCount < term)
    {
        long long newValue = prevValue + nthValue;
        prevValue = nthValue;
        nthValue = newValue;
        termCount++;
    }

    return  nthValue;
}

int main()
{
    int term = getTermCount();
    if (term < MinimumTerm)
    {
        fprintf(stderr, "Invalid Input\n");
        return EXIT_FAILURE;
    }

    printf("The %d term of the Fibonacci Sequence is %lld\n", term, getNthFibonacciTerm(term));

    return EXIT_SUCCESS;
}
\$\endgroup\$
4
\$\begingroup\$
  1. A few points about improving code

    • It seems that your naming convention for constants is to use a capitalized identifier. If so, that should be applied consistently for all constants including inputFailure.
    • The loop in the function getTermCount can be simplified. A for-loop is clearer IMO.
    • The output of getNthFibonacciTerm is actually off by one term (assuming the sequence starts with 0 at index 0). It outputs 1 for input 3. The conditional checks before the loop could also be avoided to simplify the code.
    • Since the Fibonacci sequence is non-negative, the output could use an unsigned integer to allow slightly larger inputs.
  2. About input range: since the output exceeds the limit of unsigned long long when the input is over 93, I do not see how it can be accurately represented unless you try to implement representations of big integers yourself in C.

  3. About performance: there are several \$\Theta(\log n)\$ algorithms for computing Fibonacci numbers for a given input \$n\$. If you want that, here is a list of all algorithms.

Here is an improved version:

#include <stdio.h>
#include <stdlib.h>

static const int MinimumTerm = 0;
static const int MaximumTerm = 93;
static const int MaxTries = 3;
static const int InputFailure = -1;

static int getTermCount()
{
    const char *fmtstr = "Please enter an integer value between %d and %d\n";

    for (int count = 0; count < MaxTries; count++)
    {
        int term;

        printf(fmtstr, MinimumTerm, MaximumTerm);    // IMO it is fine to just output to stdout before all attempts fail
        scanf("%d", &term);
        if (term >= MinimumTerm && term <= MaximumTerm)
        {
            return term;
        }
    }

    return InputFailure;
}

static unsigned long long getNthFibonacciTerm(int term)
{
    unsigned long long nthValue = 0;
    unsigned long long nextValue = 1;  // (n+1)th value, you may find a better name for that

    for (int termCount = 0; termCount < term; termCount++)
    {
        unsigned long long newValue = nthValue + nextValue;
        nthValue = nextValue;
        nextValue = newValue;
    }

    return nthValue;
}

int main()
{
    int term = getTermCount();
    if (term == InputFailure)
    {
        fprintf(stderr, "Invalid Input\n");
        return EXIT_FAILURE;
    }

    printf("The %d term of the Fibonacci Sequence is %llu\n", term, getNthFibonacciTerm(term));
    return EXIT_SUCCESS;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the link to the list of algorithms, I appear to be using a variant of one of them. \$\endgroup\$ – pacmaninbw Sep 9 at 14:54
  • \$\begingroup\$ Just FYI, on code review providing an alternate solution generally lowers the score you receive in an answer. You did a good job on the observations that start your answer. \$\endgroup\$ – pacmaninbw Sep 9 at 14:56
  • 1
    \$\begingroup\$ @pacmaninbw I am relatively new here. I wonder what qualifies as "an alternate solution"? Providing a brand new algorithm definitely qualifies. What about small variations that simplify the code logic (like I do here)? \$\endgroup\$ – GZ0 Sep 9 at 15:08
  • 2
    \$\begingroup\$ You can provide code that enhances your comments for certain points, such as naming conventions for the constants. Providing a full updated version of the code in the question goes too far. If I was a student that posted the code for my homework or a take home test your answer is definitely too much. Someone might take exception to to the if control construct that returns the term from the input because it isn't using a best practice such as always adding braces around the return term. \$\endgroup\$ – pacmaninbw Sep 9 at 15:22
  • \$\begingroup\$ @pacmaninbw Thanks for the clarification. I've added the braces by the way. \$\endgroup\$ – GZ0 Sep 9 at 15:28
1
\$\begingroup\$

Suggest using uint64_t (from the header file: stdint.h) rather than long long

\$\endgroup\$
  • 1
    \$\begingroup\$ Or, for an even greater range, try whether your compiler defines uint128_t. \$\endgroup\$ – Roland Illig Sep 8 at 22:58
  • \$\begingroup\$ @RolandIllig Apparently my compiler and header file don't include uint128_t. \$\endgroup\$ – pacmaninbw Sep 9 at 14:10

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.