Fibonacci numbers with the use of state machines

Fibonacci numbers are defined as follows:

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) for n >= 2

Here we show how to calculate Fibonacci numbers with the use of natural number counters as state machines. As instruction set we use PGLEcw (PGLE with conditional constructs and while loops).

    smnnc:y.succ;
    {*;
	- smnnc:x.isZero {*;
	    smnnc:z.succ;
	    smnnc:x.pred;
	*};
	- smnnc:y.isZero {*;
	    smnnc:x.succ;
	    smnnc:y.pred;
	    smnnc:z.succ;
	*};
	- smnnc:z.isZero {*;
	    smnnc:y.succ;
	    smnnc:z.pred;
	*};
	smnnc:y.dump;
    *}

We assume that x and y are the last two Fibonacci numbers. The next number is calculated as follows:

    z = x
    x = y
    y = y + z

The only operations the natural number counter provide are succ, pred, and isZero. So these assignments are done in a more primitive way.

Initially, a natural number counter has the value 0, so we start with only setting y to the value 1.
Next, we start an unconditional while loop which consist of three parts.

assign the value of x to z after which the value of x is 0
assign the value of y to x after which y becomes zero,
at the same time, the value of y is added to z which now has the value of x + y
assign the value of z to y after which z has the value 0

The last instruction of the while loop outputs the value of counter y.

We can start the simulator with the following command:

gensim -P PGLEcw -B FMN -l fibonacci

Running the program gives the following output:

    natural number counter y: 1
    natural number counter y: 2
    natural number counter y: 3
    natural number counter y: 5
    natural number counter y: 8
    natural number counter y: 13
    natural number counter y: 21
    natural number counter y: 34
    natural number counter y: 55
    natural number counter y: 89
    natural number counter y: 144
    natural number counter y: 233
    natural number counter y: 377
    natural number counter y: 610
       .
       .
       .