# Ada Programming/Algorithms/Chapter 6

## Contents

## Chapter 6: Dynamic Programming[edit]

### Fibonacci numbers[edit]

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

#### Simple Implementation[edit]

...

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`

.

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

functionFib (n : Integer_Type)returnInteger_Typeisbeginifn = 0thenreturn0;elsifn = 1thenreturn1;elsereturnFib (n - 1) + Fib (n - 2);endif;endFib; ...

#### Cached Implementation[edit]

...

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

typeCache_Typeisrange-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)

subtypeInteger_TypeisCache_Typerange0 .. 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 :constantInteger_Type := Integer_Type'Value (Ada.Command_Line.Argument (1));

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

typeCache_Arrayisarray(Integer_Typerange2 .. Value)ofCache_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.

functionFib (N : Integer_Type)returnInteger_TypeisbeginifN = 0orelseN = 1thenreturnN;elsifF (N) /= Cache_Type'FirstthenreturnF (N);elseF (N) := Fib (N - 1) + Fib (N - 2);returnF (N);endif;endFib; ...

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

typeCache_Arrayisarray(Integer_Typerange0 .. Value)ofCache_Type; F : Cache_Array := (0 => 0, 1 => 1,others=> Cache_Type'First);

and then you can remove the first `if` path.

ifN = 0orelseN = 1thenreturnN; elsifF (N) /= Cache_Type'Firstthen

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[edit]

This version looks just like the original in WikiCode.

typeInteger_Typeisrange0 .. 999_999_999_999_999_999;functionFib (N : Integer_Type)returnInteger_TypeisU : Integer_Type := 0; V : Integer_Type := 1;beginforIin2 .. NloopCalculate_Next :declareT :constantInteger_Type := U + V;beginU := V; V := T;endCalculate_Next;endloop;returnV;endFib;

#### No 64 bit integers[edit]

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.

typeInteger_Typeisdelta1.0digits18range0.0 .. 999_999_999_999_999_999.0;

You should know that floating point numbers are unsuitable for the calculation of fibonacci numbers. They will not report an error condition when the number calculated becomes too large — instead they will lose in precision which makes the result meaningless.