# Fibonacci numbers (occam)

### From LiteratePrograms

**Other implementations**: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml |**occam**| Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

- 1 \\ \end{cases} ."/>

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.

There are several different ways to approach Fibonacci number generation in occam. We'll start with the simplest, and then take a look at a less straightforward (but potentially more efficient) solution.

## Contents |

## Function

One way to compute the Fibonacci numbers is to simply use a `FUNCTION`

that finds the *n*th by computing all of the Fibonacci numbers up to *n* each time it is called. Since occam doesn't support recursion, the sequence of numbers must be computed iteratively (although occam's multiple-assignment capabilities make this easier than it might otherwise have been).

<<fibfunc>>=INTFUNCTION fib (VAL INT n)INT fib.num, next.fib.num:VALOFSEQfib.num, next.fib.num := 0, 1SEQi = 0FORn fib.num, next.fib.num := next.fib.num, (fib.num + next.fib.num)RESULTfib.num :

## Generator

An alternative approach to finding the Fibonacci numbers is to compute them in a lazy fashion, using a generator process. This approach works best when the Fibonacci numbers are required to be provided in sequence, but not necessarily needed all at the same time.

The generator process takes as arguments two channels, one for receiving commands, and one for output of a new number.

<<fibgen>>=PROC fib.gen (CHAN FIB in, CHAN INT out)fibgenbody :

The `FIB`

protocol used by the generator's command channel, `in`

, allows a process to request that a new Fibonacci number be output, and to terminate or reset the generator:

<<FIB>>=PROTOCOLFIBCASEquit reset give.num :

Internally, the generator process stores the current Fibonacci number and the next number in the sequence. These are initialized to 0 and 1 respectively whenever the generator is reset.

<<fibgenbody>>=INT fib.num, next.fib.num:PROC init ()fib.num, next.fib.num := 0, 1 :

The actual operation of the generator is purely sequential. It begins by initializing the current and next Fibonacci numbers, and then enters a loop in which it awaits commands. The loop terminates if the `quit`

message is received. The `reset`

message causes the generator to reinitialize its stored Fibonacci numbers. The `give.num`

message causes the generator to output the current Fibonacci number, and compute the next number in the sequence.

<<fibgenbody>>=SEQinit()INITIALBOOL doneISFALSE:WHILENOTdone in ?CASEquit done := TRUE reset init() give.numSEQout ! fib.num fib.num, next.fib.num := next.fib.num, (fib.num + next.fib.num)

Several additional features could be added to this simple implementation. One useful addition would be to store every computed number in an internal array. This memoization would eliminate the need to do any recomputation after a reset of the generator. Another possibility, which would work best in combination with memoization, is to provide a command that would allow a consumer to request a specific Fibonacci number.

## Testing

This simple test harness runs the various Fibonacci number implementations.

<<fibnum.occ>>=fibfunc FIB fibgenPROC fib.test (CHAN BYTE scr!)CHAN FIB tell.fib: CHAN INT from.fib: fibgenprintSEQout.string("Function:*n", 0, scr) fibfunctest out.string("*n*nGenerator:*n", 0, scr) fibgentest :

### Testing the `fib`

function

The Fibonacci function is run iteratively, and the results for each value of *n* are printed to the screen.

<<fibfunctest>>=SEQn = 0FOR40SEQout.int(fib(n), 0, scr) scr ! ' '

### Testing the generator

The Fibonacci generator process is placed in parallel with an anonymous sequential process. This sequential process prints the first 40 Fibonacci numbers, resets the generator, and then again prints the first 40 Fibonacci numbers.

<<fibgentest>>=PARfib.gen(tell.fib, from.fib)SEQfib.gen.print(40) scr ! '*n' tell.fib ! reset fib.gen.print(40) scr ! '*n' tell.fib ! quit

The actual interaction with the generator is carried out by the auxiliary`fib.gen.print`

procedure, which iteratively requests a new Fibonacci number, receives the requested number, and prints it to the screen.

<<fibgenprint>>=PROC fib.gen.print (VAL INT max.fib.num)INT fib.num:SEQn = 0FORmax.fib.numSEQtell.fib ! give.num from.fib ? fib.num out.int(fib.num, 0, scr) scr ! ' ' :

### Compilation

This occam Fibonacci number demonstration can be compiled using the Kent Retargetable occam Compiler:

kroc -lcourse -o fibnum fibnum.occ

Download code |