Ada Programming/Algorithms/Chapter 6

From Wikibooks, open books for an open world
Jump to navigation Jump to search

float

Chapter 6: Dynamic Programming[edit]

Fibonacci numbers[edit]

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

Simple Implementation[edit]

File: fibonacci_1.adb (view, plain text, download page, browse all)
...

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

File: fibonacci_2.adb (view, plain text, download page, browse all)
...

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

   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:

File: fibonacci_3.adb (view, plain text, download page, browse all)

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;
     els if 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[edit]

This version looks just like the original in WikiCode.

File: fibonacci_4.adb (view, plain text, download page, browse all)
   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[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.

File: fibonacci_5.adb (view, plain text, download page, browse all)
   type Integer_Type  is  delta 1.0  digits 18  range
     0.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.