---------------------------------------------------------------------------
-- 
--  Filename:
-- 
--    ackermann.adb
-- 
--  Description:
-- 
--    Ackermann's function "is an example of a recursive function which
--    is not primitive recursive". It is interesting from the point of
--    view of benchmarking because it "grows faster thany any primitive
--    recursive function" and gives us a lot of nested function calls
--    for little effort.
-- 
--    It is defined as follows:
--      A(0, n) = n+1
--      A(m, 0) = A(m-1, 1)
--      A(m, n) = A(m-1, A(m, n-1))
-- 
--    We use A(3,6) as the benchmark. This used to take long enough to
--    confirm the execution time with a stopwatch. Nowadays that's out
--    of the question. BTW, the value of A(4,2) has 19729 digits!
-- 
--    A (3,6) gives us 172233 calls, with a nesting depth of 511.
-- 
--  Credits:
-- 
--    Ackermann's function is named after Wilhelm Ackermann, a
--    mathematical logician who worked Germany during the first half
--    if the 20th century.
-- 
--  Revision:
-- 
--   $Id: $
-- 
---------------------------------------------------------------------------

with Report;
with Ada.Real_Time;
with Text_IO;

procedure Ackermann is

   use Report;
   use Ada.Real_Time;
   use Text_IO;

   package IO is new Text_IO.Integer_IO (Integer);
   use IO;

   Start_Time, Stop_Time : Time;

   ---------------
   -- Ackermann --
   ---------------

   function Ackermann (M, N : in Integer) return Integer is
   begin
      if M = 0 then
         return N + 1;
      elsif N = 0 then 
         return Ackermann (M - 1, 1);
      else 
         return Ackermann (M - 1, Ackermann (M, N - 1));
      end if;
   end Ackermann;

begin

   Test ("ackermann", "The Ackermann benchmark (nested)");

   Start_Time := Clock;

   declare
      Ans : Integer := ackermann (3, 6);
   begin
      if Ans /= 509 then
         Failed ("Ackermann result wrong");
      end if;   
   end;

   Stop_Time := Clock;

   Put ("Time taken = ");
   Put (Integer (1000.0 * To_Duration (Time_Span'(Stop_Time - Start_Time))), 0);
   Put (" mSec");
   New_Line;

   Result;
end Ackermann;