Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldchangelog/action.php on line 8

Strict Standards: Declaration of action_plugin_blog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/blog/action.php on line 154

Strict Standards: Declaration of action_plugin_include::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/include/action.php on line 140

Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldindex/action.php on line 57

Strict Standards: Declaration of action_plugin_discussion::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/discussion/action.php on line 955

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 205

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 208

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 389

Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 530

Strict Standards: Declaration of cache_instructions::retrieveCache() should be compatible with cache::retrieveCache($clean = true) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/cache.php on line 291

Deprecated: Function split() is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/auth.php on line 154

Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 71
nex code:ada:fibonacci
 

DSA Exercise 2 2003

I'm not putting up assignment one because I didn't get it to work, but here is programming assignment two. This was a second year computing assignment in which we had to write a Fibonacci algorithm in the programming language, Ada. Once again, I doubt you'll find this interesting or useful unless you are learning Ada or have a surreal interest in the Fibonacci algorithm.

Description

The Fibonacci algorithm was invented by an Italian mathematician (Fibonacci) to predict rabbit growth. A lot of assumptions are made, some of which are a bit sillier than others:

Assume that you start with two rabbits.
Assume that once a rabbit is three years old, it is capable of mating.
Assume that all rabbits capable of mating will in fact mate.
Assume that every time two rabbits mate, one offspring is produced without failure; no more, no less.
Assume rabbits can only produce one 'litter' a year.
Assume that there is an almost equal number of male and female rabbits.
Assume rabbits never die.

Anyway, the interesting thing about the Fibonacci algorithm is that it can be implemented recursively, and the numbers get big VERY quickly. The most basic way of expressing the algorithm is shown below:

fib[n] = fib[n-1] + fib[n-2]

where fib[1] = 1, fib[2] = 1

The Source Code

You can download all the source code (and a windows executable) of the program here or view it below. The program source is in two parts, the ex2.adb file handles the actual Fibonacci algorithm (recursively) with a pretty fast implementation. And the ListPackage files contain procedures and methods for handling large numbers beyond the constraints of the programming language. This assignment got 11/10 (that's right, it was so good I got a bonus mark).

ex2.adb:

----------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     DSA 2 Exercise 1 (ex2)                                             --
--     Program Title : Fibonacci Algorithm Version 0.9                    --
--     Author : nex                                                       --
--     Group : L                                                          --
--     Matriculation Number : ***ROMOVED FROM ONLINE VERSION***           --
--     Date Last Modified : 15th December 2003                            --
--                                                                        --
--     Description : This program takes in two integers from standard     --
--                   input and uses them as indices to calculate          --
--                   Fibonacci numbers from the lower to upper index.     --
--                                                                        --
--                   This program uses ListPackage for representing       --
--                   large integer values.                                --
--                                                                        --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
----------------------------------------------------------------------------
 
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Listpackage; use Listpackage;
 
 
procedure ex2 is
 
   -- Variables
   L    : Integer;
   U    : Integer;
 
   Swap : Integer;
   V    : Boolean;
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   -- The Fib function calculates the value of the Fibonacci
   -- number with index n.
   function Fib (n : in integer) return Big is
 
 
      -------------------------------------------------------------
      -------------------------------------------------------------
      -- helpFib is used to speed up the Fib function by 
      -- preventing repeated calculations.
      function helpFib (n     : in integer;
                        k     : in integer;
                        fibk  : in Big    ;
                        fibk1 : in Big     ) return Big is
      begin
         if n = k then
            return fibk;
         else
            return helpFib(n, k+1, Add(fibk,fibk1), fibk);
         end if;
      end Helpfib;
      -------------------------------------------------------------
      -------------------------------------------------------------
 
 
      -- These Big values are required as input into the 
      -- helpFib function.
      One  : Big;
      Zero : Big;
 
   begin
 
      MakeOne(One);
      Makezero(Zero);
 
      -- For values less than 3, the Fib number is 1;
      if N < 3 then
         return One;
 
      -- For indices smaller than 21, use a recursive Fib function
      elsif N < 21 then
         return(Add(Fib(N-2), Fib(N-1)));  
 
      -- For indices larger than 20, use the helpFib function to
      -- speed things up.
      else
         return(helpFib(n, 1, One, Zero));
      end if;
 
   end Fib;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   -- The Verify procedure tests to see if the Fibonacci number
   -- calculated is accurate by trying to find it by a different 
   -- algorithm and then comparing it to the originally found 
   -- value.
   procedure Verify (N: in     Integer;
                     V:    out Boolean ) is
   test : big;
   begin
      if N /= 2 then
         Test := Fib(N);
 
         -- The Add function is taken from ListPackage
         Test := Add(Add(Test,Test),Test);
 
         -- IsEqual is taking from ListPackage
         if IsEqual(Test, (Add(Fib(N+2), Fib(N-2)))) then
            V := True;
         else
            V := False;
         end if;
      else
         V := True;
      end if;
 
   end Verify;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
-- Start of main program --
begin
 
   -- Get the indices to be used
   Get(L);
   Get(U);
 
   -- Check that numbers are in the correct range
   if (L < 1) or (U < 1) then
      Put ("Fibonacci Indices must be positive integers greater than zero.");
   else
 
      -- If indices are entered in the wrong order, reverse them
      if L > U then
         Swap := U;
         U := L;
         L := Swap;
      end if;
 
      -- Output the Fibonacci Numbers specified
      For I in L..U loop
         New_Line;
         Put("Fib(");
         Put(I,2);
         Put(") = ");
 
         -- WriteBig is from ListPackage
         Writebig(Fib(I));
 
         -- Verify that the calculated value is correct
         Verify(I,V);
         if V then
            Put ("  Valid");
         else
            Put ("  Invalid");
         end if;
 
      end loop;      
   end if;
 
end ex2;

ListPackage.ads:

----------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     DSA 2 Exercise 1 (ex2)                                             --
--     Program Title : ListPackage Version 0.9                            --
--     Author : nex                                                       --
--     Group : L                                                          --
--     Matriculation Number : **REMOVED FROM ONLINE VERSION***            --
--     Date Last Modified : 15th December 2003                            --
--                                                                        --
--     Description : This package contains functions and procedures for   --
--                   storing and manipulating large integers              --
--                                                                        --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
----------------------------------------------------------------------------
 
package ListPackage is
 
   -- Type Big contains large integer values
   type Big is private;
 
   function Add(x,y:Big) return Big;
   -- Calculates x+y and returns as type big
 
   function IsEqual(x,y:Big) return Boolean;
   -- Returns the boolean expression x=y
 
   procedure MakeOne(One: out Big);
   -- Make the value 1 of type Big
 
   procedure MakeZero(One: out Big);
   -- Make the value 1 of type Big
 
   procedure WriteBig(x:Big);
   -- Writes the value of x
 
private
 
   -- Type big is stored as a record of
   -- linked lists so that, in theory, it 
   -- will never have an integer so large
   -- that it cannot be stored in Big.
   type N;
   type Big_L is access N;
   type N is
      record
         Next : Big_L;
         Prev : Big_L;
         Val  : Integer;
   end record;
 
   type Big is
      record
         Head : Big_L;
         Tail : Big_L;
   end record;
 
end ListPackage;

ListPackage.adb

----------------------------------------------------------------------------
----------------------------------------------------------------------------
--                                                                        --
--     DSA 2 Exercise 1 (ex2)                                             --
--     Program Title : ListPackage Version 0.9                            --
--     Author : nex                                                       --
--     Group : L                                                          --
--     Matriculation Number : ***REMOVED FROM ONLINE VERSION***           --
--     Date Last Modified : 15th December 2003                            --
--                                                                        --
--     Description : This package contains functions and procedures for   --
--                   storing and manipulating large integers              --
--                                                                        --
--                                                                        --
--     State of Program: The program has worked correctly for all test    --
--                       data.                                            --
--                                                                        --
----------------------------------------------------------------------------
----------------------------------------------------------------------------
 
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Text_Io; use Ada.Text_Io;
package body ListPackage is
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   function Add(X,Y:Big) return Big is
   -- Calculates x+y and returns as type big
      X_Temp : Big;
      Y_Temp : Big;
      R      : Big;
      R_Temp : Big;
      C, S, P, Q   : Integer;      
   begin
 
      -- Clear variables of data
      C := 0;
      S := 0;
      P := 0;
      Q := 0;
      R_Temp.Head := null;
      R_Temp.Tail := null;
      R.Head := null;
      R.Tail := null;
 
      -- Assign X and Y to worker variables
      X_Temp := X;
      Y_Temp := Y;
 
      -- If X or Y have no values, return R (which will = null)
      if (X.Head /= null) or (Y.Head /= null) then
 
         -- If there is still data in the current X_Temp or Y_Temp or there
         -- is a carry, get intermediate values for use in equations
         while (X_Temp.Head /= null) or (Y_Temp.Head /= null) or (C = 1) loop
            if (X_Temp.Head = null) and (Y_Temp.Head /= null) then
               Q := Y_Temp.Head.all.Val;
               Y_Temp.Head := Y_Temp.Head.all.Next;
               P := 0;
            elsif (X_Temp.Head /= null) and (Y_Temp.Head = null) then
               P := X_Temp.Head.all.Val;
               X_Temp.Head := X_Temp.Head.all.Next;
               Q := 0;
            elsif (X_Temp.Head = null) and (Y_Temp.Head =null) then
               P := 0;
               Q := 0;
            else
               P := X_Temp.Head.all.Val;
               X_Temp.Head := X_Temp.Head.all.Next;
               Q := Y_Temp.Head.all.Val;
               Y_Temp.Head := Y_Temp.Head.all.Next;
            end if;
 
            -- Use intermediate values to calculate sum and carry
            if R.Head = null then
               S:= (P + Q) rem 1000;
               C:= (P + Q) / 1000;
            else
               S:= (P + Q + C) rem 1000;
               C:= (P + Q + C) / 1000;
            end if;
 
            -- Add new nodes containing correct values
            -- to doubly linked list
            if R.Head = null then
               R.Head := new N'(null, null, S);               
               R.Tail := R.Head;
            else
               R.Tail.all.Next := new N'(null, null, S);
               R_Temp := R;
               R.Tail := R.Tail.all.Next;
               R.Tail.all.Prev := R_Temp.Tail;               
            end if;
         end loop;
 
      end if;
      return R;
   end Add;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   function IsEqual(x,y:Big) return Boolean is
   -- Returns the boolean expression x=y
      X_Temp : Big;
      Y_Temp : Big;
   begin
 
      -- Assign X and Y to worker variables
      X_Temp := X;
      Y_Temp := Y;
 
      -- Test all possible cases in which X = Y (or X /= Y)
      -- using recursion to call all nodes.
      if (X_Temp.Head /= null) and (Y_Temp.Head /= null) then
         if (X_Temp.Head.all.Val = Y_Temp.Head.all.Val) then
            X_Temp.Head := X_Temp.Head.all.Next;
            Y_Temp.Head := Y_Temp.Head.all.Next;
            return Isequal(X_Temp, Y_Temp);
         else
            return False;
         end if;
      elsif (X_Temp.Head /= null) and (Y_Temp.Head = null) then
         return False;
      elsif (X_Temp.Head = null) and (Y_Temp.Head /= null) then
         return False;
      elsif (X_Temp.Head = null) and (Y_Temp.Head = null) then
         return True;
      else
         return False;
      end if;
 
   end IsEqual;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   procedure MakeOne(One: out Big) is
   -- Make the value 1 of type Big      
      One_L : Big_L;
   begin      
      One_L := null;
      One_L := new N;
      One_L.all.Val := 1;
      One_L.all.Next := null;
      One_L.all.Prev := null;
      One.Head := One_L;
      One.Tail := One_L;               
   end Makeone;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   procedure MakeZero(One: out Big) is
   -- Make the value 0 of type Big
   -- This is required for the helpFib function to work      
      One_L : Big_L;
   begin      
      One_L := null;
      One_L := new N;
      One_L.all.Val := 0;
      One_L.all.Next := null;
      One_L.all.Prev := null;
      One.Head := One_L;
      One.Tail := One_L;               
   end MakeZero;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
 
   ----------------------------------------------------------------
   ----------------------------------------------------------------
   procedure WriteBig(x:Big) is
   -- Writes the value of x to standard output
      X_Temp : Big;
   begin
 
      -- Assign X to a worker variable
      X_Temp := X;
      if X.Tail /= null then
         if X.Tail.all.Next /=null then
            if X.Tail.all.Val < 100 then
               if X.Tail.all.Val < 10 then
                  Put ("00");
               else
                  Put ("0");
               end if;
            end if;
         end if;
 
         -- Output current node value then
         -- recursively call other node values
         -- for output.
         Put (X.Tail.all.Val,1);
         X_Temp.Tail := X_Temp.Tail.all.Prev; 
         WriteBig(X_Temp); 
      end if;
   end WriteBig;
   ----------------------------------------------------------------
   ----------------------------------------------------------------
 
end ListPackage;

Example of Use

To use the program enter the low number you want the Fibonacci sequence to start from then the high number you want it to finish with.

Input (each end of line is an enter'):

4
600

Output:

Fib(n) = fibnumber Valid OR Invalid
Fib(n + 1) = next_fibnumber Valid OR Invalid

Assumptions

None, but for large Fibonacci indices, the computer may crash from running out of memory.

Nexami Engeo 2007/07/05 17:16


Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 79