## Chapter 6: Dynamic Programming

### Fibonacci numbers

The following codes are implementations of the Fibonacci-Numbers examples.

#### Simple Implementation

```...
```

To calculate Fibonacci numbers negative values are not needed so we define an integer type which starts at 0. With the integer type defined you can calculate up until `Fib (87)`. `Fib (88)` will result in an `Constraint_Error`.

```  type Integer_Type is range 0 .. 999_999_999_999_999_999;
```

You might notice that there is not equivalence for the `assert (n >= 0)` from the original example. Ada will test the correctness of the parameter before the function is called.

```  function Fib (n : Integer_Type) return Integer_Type is
begin
if n = 0 then
return 0;
elsif n = 1 then
return 1;
else
return Fib (n - 1) + Fib (n - 2);
end if;
end Fib;

...
```

#### Cached Implementation

```...
```

For this implementation we need a special cache type can also store a -1 as "not calculated" marker

```  type Cache_Type is range -1 .. 999_999_999_999_999_999;
```

The actual type for calculating the fibonacci numbers continues to start at 0. As it is a subtype of the cache type Ada will automatically convert between the two. (the conversion is - of course - checked for validity)

```  subtype Integer_Type is Cache_Type range
0 .. Cache_Type'Last;
```

In order to know how large the cache need to be we first read the actual value from the command line.

```  Value : constant Integer_Type :=
```

The Cache array starts with element 2 since Fib (0) and Fib (1) are constants and ends with the value we want to calculate.

```  type Cache_Array is
array (Integer_Type range 2 .. Value) of Cache_Type;
```

The Cache is initialized to the first valid value of the cache type — this is `-1`.

```  F : Cache_Array := (others => Cache_Type'First);
```

What follows is the actual algorithm.

```  function Fib (N : Integer_Type) return Integer_Type is
begin
if N = 0 or else N = 1 then
return N;
elsif F (N) /= Cache_Type'First then
return F (N);
else
F (N) := Fib (N - 1) + Fib (N - 2);
return F (N);
end if;
end Fib;

...
```

This implementation is faithful to the original from the Algorithms book. However, in Ada you would normally do it a little different:

when you use a slightly larger array which also stores the elements 0 and 1 and initializes them to the correct values

```  type Cache_Array is
array (Integer_Type range 0 .. Value) of Cache_Type;

F : Cache_Array :=
(0      => 0,
1      => 1,
others => Cache_Type'First);
```

and then you can remove the first if path.

```     if N = 0 or else N = 1 then
return N;
elsif F (N) /= Cache_Type'First then
```

This will save about 45% of the execution-time (measured on Linux i686) while needing only two more elements in the cache array.

#### Memory Optimized Implementation

This version looks just like the original in WikiCode.

```  type Integer_Type is range 0 .. 999_999_999_999_999_999;

function Fib (N : Integer_Type) return Integer_Type is
U : Integer_Type := 0;
V : Integer_Type := 1;
begin
for I in  2 .. N loop
Calculate_Next : declare
T : constant Integer_Type := U + V;
begin
U := V;
V := T;
end Calculate_Next;
end loop;
return V;
end Fib;
```

#### No 64 bit integers

Your Ada compiler does not support 64 bit integer numbers? Then you could try to use decimal numbers instead. Using decimal numbers results in a slower program (takes about three times as long) but the result will be the same.

The following example shows you how to define a suitable decimal type. Do experiment with the digits and range parameters until you get the optimum out of your Ada compiler.

```  type Integer_Type is delta 1.0 digits 18 range