# Basic Fibonacci sequence in C

#include <stdio.h>
#include <stdlib.h>
#define RED     "\x1b[31m"
#define GREEN   "\x1b[32m"
#define YELLOW  "\x1b[33m"
#define BLUE    "\x1b[34m"
#define MAGENTA "\x1b[35m"
#define CYAN    "\x1b[36m"
#define RESET   "\x1b[0m"

int main () {

int n1 = 1, n2 = 0, i = 0, limit = 0, neg = 0, pos = 0;
printf("Enter first number > ");
scanf("%d",&n1);
printf("Enter the seconed number > ");
scanf("%d",&n2);
printf("Enter the number of terms > ");
scanf("%d",&limit);

for (i; i < limit; i++ ) {
if (n2 >=1) { pos ++; printf( RESET "%i\n" RESET, n2); }
if (n2 <=0) { neg ++; printf( MAGENTA   "%i\n" MAGENTA,  n2); }
int temp = n2;

n2 += n1;
n1 = temp;
}

printf(RESET"\n***************************************************"RESET);
printf("\nPositive numbers in range %i : %i\n",limit,pos);
printf("Negitive : %i",neg);
printf("\n***************************************************");
}

• -1 Please provide the problem description and your desired level of review at a bare minimum. Questions solely comprising "Code!" merit only "You posted some code which probably could be improved" as a response. If this is your desired response, simply email your code to yourself. Everyone wins! :p – David Harkness Apr 12 '14 at 2:09

# Things you could improve

### Using Headers

• Right now you are defining some items at the top of your source file.

#define RED     "\x1b[31m"
#define GREEN   "\x1b[32m"
#define YELLOW  "\x1b[33m"
#define BLUE    "\x1b[34m"
#define MAGENTA "\x1b[35m"
#define CYAN    "\x1b[36m"
#define RESET   "\x1b[0m"


These are all relatable, and reusable ANSI escape codes to color your text in a terminal, so you could put them all in their own header (color.h) for easy use with other files.

#define BLACKTEXT(x) "\033[30;1m" x "\033[0m"
#define REDTEXT(x) "\033[31;1m" x "\033[0m"
#define GREENTEXT(x) "\033[32;1m" x "\033[0m"
#define YELLOWTEXT(x) "\033[33;1m" x "\033[0m"
#define BLUETEXT(x) "\033[34;1m" x "\033[0m"
#define MAGENTATEXT(x) "\033[35;1m" x "\033[0m"
#define CYANTEXT(x) "\033[36;1m" x "\033[0m"
#define WHITETEXT(x) "\033[37;1m" x "\033[0m"


Then you can just #include "color.h" in all of your files where you need some color in your terminal.

• As you can see from my own color.h header file, I don't have a RESET macro. I didn't find a use for it, since I would always end up resetting the color right after I used it. The way I have it defined, my macros can do that for me.

### User Experience

• I find it useless to have to enter a first and second number.

        printf("Enter first number > ");
scanf("%d",&n1);
printf("Enter the seconed number > ");
scanf("%d",&n2);


What is the point of this? Just start from $0$ and $1$, and go to $n$ number of terms.

### Efficiency/Algorithm

• Right now you can't compute that many fibonacci numbers, because of the maximum size of an int; you can only calculate numbers up to 32767.

We aren't expecting negative numbers in our sequence, so we easily increase this restriction, you could use an unsigned int which has a maximum value of 65535, or even better, a long long unsigned int with a maximum value of 18446744073709551615. That's 562967131565294 times larger than your current program!

• Your algorithm can be simplified down using method extraction and recursion.

  for (i; i < limit; i++ ) {
if (n2 >=1) { pos ++; printf( RESET "%i\n" RESET, n2); }
if (n2 <=0) { neg ++; printf( MAGENTA   "%i\n" MAGENTA,  n2); }
int temp = n2;

n2 += n1;
n1 = temp;
}


Move the computing of the fibonacci sequence to it's own method. All you should be passing it is the number of the term you want to compute.

unsigned long long int fibonacci(unsigned long long int n)
{
if (memoization[n] != -1) return memoization[n];

return (n < 2)? n : (memoization[n] = fibonacci(n-1) + fibonacci(n-2));
}

• You might notice that I have included an array in my previous point named memoization. We want to use this to decrease computation time with the recursion. Basically, if we have already computed a number, we put it into the array so we don't have to calculate it the next time we want to find a fibonacci number. If we haven't found the number, we can indicate that in the array by storing a -1 there instead.

### Style

• Put all of your variable declarations to separate lines. From Code Complete, 2nd Edition, p. 759:

With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.

• I can't follow your tabbing scheme.

        printf("Enter first number > ");
scanf("%d",&n1);
printf("Enter the seconed number > ");
scanf("%d",&n2);
printf("Enter the number of terms > ");
scanf("%d",&limit);


This makes it harder for me to read. You should align all of the left characters in a block to make them more readable.

• You should declare your parameters as void if you don't take in any arguments.

int main(void)


### Standards

• You should be declaring i inside of your for loops.(C99)

for (int i = 0; i < limit; i++)


# Final code:

• ### Iterative: $O(1)$

The calculation of the fibonacci sequence here is a bit different than my point I made above. I didn't mention it, since it was so different than how you were calculating your sequence. This is one of the most optimal solutions for calculating a fibonacci sequence.

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

long long unsigned int fibonacci(long long unsigned int n)
{
return round((1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n)));
}

int main(void)
{
unsigned int num = 0;

printf("Enter how far to calculate the series: ");
if (scanf("%i", &num) <= 0)
{
puts("Invalid input.");
return -1;
}

for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
}

• ### Recursion: $O(n)$

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

#define ARRAYLENGTH 100 // keep in mind the result must fit in an llu int (fibonacci values grow rapidly)
// you will run into issues after 93, so set the length at 100
long long int memoization[ARRAYLENGTH];

long long unsigned int fibonacci(long long unsigned int n)
{
if (memoization[n] != -1) return memoization[n];

return (n < 2)? n : (memoization[n] = fibonacci(n-1) + fibonacci(n-2));
}

int main(void)
{
unsigned int num = 0;

for(unsigned int i = 0; i < ARRAYLENGTH; i++) memoization[i] = -1; // preset array

printf("Enter how far to calculate the series: ");
if (scanf("%i", &num) <= 0)
{
puts("Invalid input.");
return -1;
}
if (num < ARRAYLENGTH)
{
for(unsigned int n = 1; n < num + 1; ++n) printf("%llu\n", fibonacci(n));
}
else
{
puts("Input number is larger than the array length.");
return -2;
}
}

• Minor quibble: signed to unsigned doubles the maximum value, but you specify the same value for both. – David Harkness Apr 12 '14 at 2:17
• @DavidHarkness Turns out I had the wrong values in there for some reason. They have been fixed, thanks! – syb0rg Apr 12 '14 at 2:25
• Iterative is O(1) .... really? – rolfl Apr 12 '14 at 23:58
• @rolfl I was more looking inside of the loop, within the function call. – syb0rg Apr 13 '14 at 0:19
• I would like to point out that the boundaries you gave for different types are true on most modern platforms, but they are not given by any standard. long is usually already 64-bits on UNIX systems whereas it's 32-bit on Windows, where you'll need to use long long. I strung suggest using <inttypes.h>and then using fixed size types such as uint64_t where applicable. – Cu3PO42 Apr 16 '14 at 17:25

Short style comment, you will avoid much future pain by using fgets() into a buffer and then sscanf() to convert the buffer data to a type rather than using scanf() directly.

For more detail, see the comp.lang.c FAQ.

• Yes, but the C11 standard gets_s() (that replaces gets()) would be a better option. – syb0rg Apr 11 '14 at 23:51
• Thanks! That's what I get for being an old-timer... hadn't caught up to C11 yet b/c the environment I code in doesn't have compliant compilers on all platforms. – JohnH Apr 12 '14 at 3:37
• Your welcome! I'm still adjusting to the new standards myself. Hopefully you can stick around and learn them with me! – syb0rg Apr 12 '14 at 3:39
• @syb0rg C11dr spec K.3.5.4.1 6 gets_s() has the recommended practice of "... Consider using fgets (...) instead of gets_s. ...". IMO, gets_s() is a good replacement for gets(), but fgets() is better than both of them. (especially with that pesky gets_s() rsize_t type. – chux - Reinstate Monica May 1 '14 at 18:03