PGA - ProGram Algebra

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

more info on Fibonacci numbers

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.

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
       .
       .
       .