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 8
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_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
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_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 157
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
====== 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 [[http://www.n-e-x.co.uk/files/fib.zip|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.
--- //[[nex@n-e-x.co.uk|Nexami Engeo]] 2007/07/05 17:16//
~~DISCUSSION~~