How those variables works in this Fibonacci algorithm?

Question

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

using namespace std;

#define tip long
tip z;

tip Fibonacci(tip n ){
    tip i = 1, j = 0, k = 0, h = 1, t = 0;
    while( n > 0 )
    {
        z++;
        if( ((long) n) % 2 )
        {
            t = j * h;
            j = i * h + j * k + t;
            i = i * k + t;
        }
        t = h * h;
        h = 2 * k * h + t;
        k = k * k + t;
        n = n / 2;
     }
     return j;
}

int main()
{
    z = 0;
    cout << "\n\n\n 5th = " << Fibonacci( 5 );
    cout << "\n Nr. of iterations = " << z;

    z = 0;
    cout << "\n\n 10th = " << Fibonacci( 10 );
    cout << "\n Nr. of iterations = " << z;

    z = 0;
    cout << "\n\n 20th = " << Fibonacci( 20 );
    cout << "\n Nr. of iterations = " << z;

    z = 0;
    cout << "\n\n 40th = " << Fibonacci( 40 );
    cout << "\n Nr of iterations = " << z;
    cout << "\n\n";

    return 0;
}

I have this program just like that. Without comments, variables with meaningless names.

The program is working. No errors, or something else. It just shows the number value and number of iterations.

Questions :

I don't understand what those variables ( *i, j, k, h, t* ) mean?
What they do in this algorithm?
What algorithm is this?

i, j, k, h, t are examples of bad variable names. Variable names should be descriptive, their names should give the reader some clue of their purpose. — Imran Ali, Jun 21 '18 at 11:10
C and C++ are different programming languages. Your code is not some [MCVE] so your question is off-topic here. I recommend compiling a full program with all warnings and debug info (so `gcc -Wall -Wextra -g` with [GCC](http://gcc.gnu.org/)) and running it in some debugger (e.g. [using the `gdb` debugger](https://sourceware.org/gdb/current/onlinedocs/gdb/)...) -perhaps step by step- to understand its behavior. — Basile Starynkevitch, Jun 21 '18 at 11:13
Are any of the links in this answer helpful? https://stackoverflow.com/a/1526036/909655 — Mats, Jun 21 '18 at 11:16
BTW, you'll better read more on [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number), and this becomes a math question (off-topic on StackOverflow), not a C one. — Basile Starynkevitch, Jun 21 '18 at 11:17
You have not searched enough. Did you go into some math library to study much more the Fibonacci sequence? You could spend months on that — Basile Starynkevitch, Jun 21 '18 at 11:19
@BasileStarynkevitch: Not having an MVCE does not make a question off-topic. As the page you link to states, at the start, it is for “When asking a question about a problem caused by your code.” But this question is not asking about a problem caused by code. It is asking about how some code, likely taken from a textbook, works. It does not need to be debugged and has adequate context. — Eric Postpischil, Jun 21 '18 at 12:11
The debugger is very useful to understand the behavior of someone's else code. It is not only useful on your own code — Basile Starynkevitch, Jun 21 '18 at 12:29
The answer I was looking for. Came from @Mats. https://stackoverflow.com/a/1526036/909655 — Hejea, Jun 21 '18 at 15:26

score 5 · Accepted Answer · answered Jun 21 '18 at 11:19

5

This snippet calculates individual entries of the Fibonacci sequence by matrix exponentiation. The variables i,j,k,h encode the matrix [1,0;0,1]. The variable t is a temporary variable. The whole thing is most probably an example of how to not do it: no comments, no useful variable names, no checks for overflow, and so on.

answered Jun 21 '18 at 11:19

deamentiaemundi

5,502
2
12
20

1

The name `Fib3` and the file-scope identifier `z` used to count iterations are clues: This is not **merely** code to calculate Fibonacci numbers. It comes from a textbook or tutorial which previously showed `Fib1` and `Fib2`. The original material undoubtedly contains discussion (in particular using `z` to demonstrate that some methods do less work than others), so your criticisms about lack of comments and variable names are unwarranted—the information was present in the original source material but was removed by the OP, not omitted by its author. – Eric Postpischil Jun 21 '18 at 12:18
1

@EricPostpischil I'm supposed to only take what's in the OP. Assuming too much gets me hit over my head and assuming too little gets me hit over my head. Whatever I do ... ;-) Oh, and it is most probably Gilles Brassard and Paul Bratley: "Algorithmics: theory and practice". The variable naming scheme fits and it was the first hit (for me!) at books.google.com. A version with pseudocode is available as a PDF online. Don't know if it's a legal upload but I doubt it, hence no link. – deamentiaemundi Jun 21 '18 at 12:54

How those variables works in this Fibonacci algorithm?

1 Answers1