How Fibonacci Series are generated using 1 Variable?

-6

What I am not understanding: How the code is able to generate all the Fibonacci series using just one variable?

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

int main (void) {
    unsigned long i = 1;
    printf ("0\n");
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
        printf ("%d\n", i & 0xffff);
        i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
    }
    return 0;
}

Reference: Fabonacci Series using one variable

c
algorithm
fibonacci
asked on Stack Overflow Sep 29, 2017 by Zahid Khan • edited Aug 24, 2020 by Zahid Khan

2 Answers

0

I don't see why this is hard?
Written in C, demonstrated on IDEOne:

#include <stdio.h>

int fib(int n)
{
    return (n == 0 || n == 1) ?  n : fib(n-1) + fib(n-2);
}

int main(void) {
    int n;
    for(n=0; n<10; ++n)
        printf("[%d] : %d\n", n, fib(n));

    return 0;
}

I only see 1 variable.
Does that not meet your requirement?

Output

[0] : 0
[1] : 1
[2] : 1
[3] : 2
[4] : 3
[5] : 5
[6] : 8
[7] : 13
[8] : 21
[9] : 34

If you want to be tricky, use the wonderful expression n==!!n?n:

int fib(int n)
{
    return n==!!n?n: fib(n-1) + fib(n-2);
}
answered on Stack Overflow Sep 29, 2017 by abelenky • edited Sep 29, 2017 by abelenky
0

I saw the answer here: Fibonacci using 1 variable

as suggested by one of the answers. Although the closed form solution is generally hard to come by unless you know how to solve Difference equations and solve the fibonacci recurrance

Fn = Fn-1 + Fn-2

I think the better way is the linear algebra.

enter image description here

The proof can be done easily by induction. Also the matrix multiplication will take O(lgn).


User contributions licensed under CC BY-SA 3.0