How to increase the speed of computed Fibonacci caluculations - C

Question

I wrote a small program to compute Fibonacci numbers:

#include <stdio.h>

int main()
{
    int first, second, final;

    first = 0;
    second = 1;
    printf("0\n1\n"); /* I know this is a quick fix, but the program still works */
    while (final <= 999999999999999999) {
        final = first + second;
        first = second;
        second = final;
        printf("%d\n", final);
    }
}

Is there any way to increase the speed in which this program computes these calculations? Could you possible explain the solution to me (if it exists)?

Thanks.

Answer 1

Of course it's possible! :)

First of all, please note you're using signed int for your variables, and max int on a 32 bit machine is 2,147,483,647 which is approx. 10^8 times smaller than the max number you're using, which is 999,999,999,999,999,999. I'll recommend to change the max num to INT_MAX (You'll need to include "limits.h")

Edit: In addition, as said in the comments to my answer, consider changing to unsigned int. you need only positive values, and the max number will be twice higher.

2nd Edit: That being said, when final will reach the closest it can to the limit in the condition, the next time its promoted, it'll exceed INT_MAX and will result in an overflow. That means here, that the condition will never be met. Better to just change the condition to the times you want the loop to run. Please note though, that any fibonacci number larger than the max numder that can be stored in your variable type, will result in an overflow.

Secondly, final isn't initialized. Write final = 0 to avoid errors.

I recommend turning on all the warnings in your compiler. It could catch many errors before they compile :) Also, I see no reason not to initialize the variables when you declare them. The value is already known.

Now for the speed of the program: I'm not sure to which extent you're willing to change the code, but the simplest change without changing the original flow, is to make less calls to printf().

Since printf() is a function that will wait for a system resource to become available, this is probably the most time consuming part in your code.

Maybe consider storing the output in a string, and lets say every 100 numbers print the string to the screen.

Try maybe to create a string, with a size of (10 (num of chars in an int) + 1 (new line char) )* 100 (arbitrary, based on when you'll want to flush the data to the screen)

Consider using sprintf() to write to a string in the inner loop, and strcat() to append a string to another string. Then, every 100 times, use printf() to write to the screen.

Answer 2

As already stated in other answers, you have obvious two problems. 1) The missing initialization of final and 2) that your loop condition will result in an endless loop due to 999999999999999999 being larger than any integer value.

The real problem here is that you use a fixed number in the condition for the while.

How do you know which number to use so that you actually calculates all the Fibonacci numbers possible for the used integer type? Without knowing the numbers in advance you can't do that! So you need a better condition for stopping the loop.

One way of solving this to check for overflow instead - like:

while (second <= (INT_MAX - first)) {  // Stop when next number will overflow

The above approach prevents signed overflow by checking whether the next first + second will overflow before actually doing the first+second. In this way signed overflow (and thereby UB) is prevented.

Another approach is to use unsigned integers and deliberately make an overflow (which is valid for unsigned int). Using unsigned long long that could look like:

unsigned long long first, second, next;

first = 1;
second = 1;
printf("1\n1\n");

next = first + second;
while (next > second) {     // Stop when there was an overflow
    printf("%llu\n", next);
    first = second;
    second = next;
    next = first + second;
}

Answer 3

Speed isn't your problem. You have an infinite loop:

while (final <= 999999999999999999) {

final has type int. Most likely int is 32-bit on your system, which means the maximum value it can hold is 2147483647. This will always be smaller than 999999999999999999 (which is a constant of type long long), so the loop never ends.

Change the datatype of your variables to long long and the loop will terminate after about 87 iterations. Also, you'll need to change your printf format specifier from %d to %lld to match the datatype printed.

Answer 4

Why are you asking this question?

If it's the intention to increase the performance, you might go for the formula of the n-th Fibonacci number, which is something like:

((1+v5)/2)^n + ((1-v5)/2)^n, something like that (v5 being the square root of 5).

If it's about learning to increase performance, you might do a code review or use performance diagnostics tools.