Fibonacci algorithm in C-CodePudding

I am trying to rewrite a fibonacci algorithm from python to C, but am having some problems. Below is the algorithm in python and I get the correct answer, but after writing in C:

def fib(n):
    a, b = 1,1
    for i in range(n):
        a, b = a b, a
        print(a, b)
    return b
    
print(fib(8))

When I wrote it in C, I get the powers of 2 - I am not sure how and if possible to correct it.

#include<stdio.h>


int fib(n){
    int a = 1;
    int b = 1;
    for (int i=0; i<n; i  ){
        a = a b;
        b = a;
    }
    return b;
}



int main(void){
    int n;
    printf("Enter the # of the fibonacci number in sequence:");
    scanf("%d", &n);
    int r = fib(n);
    printf("%d\n", r);

}

CodePudding user response：

Just add a 3rd variable for extra handling

#include <stdio.h>

int fib(int n) {
    int a, b, c;
    a = 0;
    b = 1;
    c = 0;
    for (int i = 0; i < n; i  ) {
        a = b c;
        b = c;
        c = a;
    }
    return a;
}

int main() {
    int n;
    n = fib(10); // 55
    printf("%d\n", n);
}

CodePudding user response：

Zero is a Fibonacci number too!

Try:

int fib(int n){
    int a = -1;
    int b = 1;
    for (int i = 0; i < n; i  ) {
        int t = a   b;
        a = b;
        b = t;
    }
    return b;
}

Also, none of the answers so far (including this one) account for signed integer overflow which is undefined in C. Though, for a trivial program like this it's okay to ignore it. When n is greater than 47 it overflows on my pc.

CodePudding user response：

It can be done with just two variables with a simple change b = a-b. However, an optimizing compiler will use a third register as a temp variable instead of doing b = a - b;

#include<stdio.h>

int fib(n){
    int a = 1;
    int b = 0;
    for (int i = 0; i < n; i  ){
        a = a b;
        b = a-b;
    }
    return b;
}

int main(void){
    int n;
    printf("Enter the # of the fibonacci number in sequence:");
    scanf("%d", &n);
    int r = fib(n);
    printf("%d\n", r);
    return 0;
}

CodePudding user response：

In Python, when a multiple assignment statement is executed, all expressions on the right-hand side are evaluated using the current values of the variables, and then these values are bound to the variables given in the left-hand side. For example, the statement

a, b = a b, a

evaluates both the expressions a b and a, using the current values of a and b, and then binds these values to a and b, respectively. If the current values are a=1, b=1, then the expressions have values 1 1=2 and 1, respectively, and so we get a=2, b=1.

However, your C code executes the two statements a=a b and b=a in sequence, rather than in parallel (like Python does). First the expression a b is evaluated (if a=1, b=1, then a b=2), and its value is bound to the variable a (so a is 2), and finally the expression a in the second statement is evaluated (it has value 2), and its value is bound to b (so b=2). If you want to use the original value of a (a=1) in the statement b=a, then you must store that original value in a temporary variable before overwriting a by a b, as follows:

temp=a;
a=a b;
b=temp;

In general, you can figure out yourself what is wrong with the program by learning to do a hand simulation of the program, where you write down (on paper) the current values of each variable in the program. For example, you can write the variables a and b in separate lines, with their initial values 1 and 1, respectively, next to them. Each time you execute an assignment statement, evaluate the expression on the right-hand side using the current values, and overwrite the left-hand-side variable with this new value. So, when you encounter a=a b, you would evaluate a b to be 2 (using the current values), and then cross out the current value of 1 for a and replace it by 2. In this manner, you can obtain the output using pencil and paper, and figure out what is wrong with the program.