Bug or feature?

[Laurent <daemon2@internet.lu>]

Hi

While studying recursion I tried to develop an iterative version of the fibonacci sequence.

It works but on N>47 the function outputs negative numbers,buffer overflow. No difference between my iterative version and the recursive one given in the book (recursion is quite slow...).

Build a small test program which throws a Constraint error. So why does the test functions correctly where as the fibonacci program doesn't?

I have added an Exception for the buffer overflow to the iterative version to check if this solves the problem and it does.

Positive is defined as : subtype Positive is Integer range 1 .. Integer'Last;
So if the result gets negative it should raise an constraint error without needing to add a raise myself?

Output of fibonacci:

Please enter an integer (>= 1) > 50

The fibonacci sequence for N = 50 is: 
1
1
2
3
5
8
13
21
34
55
.
.
.
1134903170
1836311903
-1323752223  <==
512559680
-811192543 <==
-298632863 <==
[2014-05-14 20:57:08] process terminated successfully (elapsed time: 02.29s)

Output of buffer_overflow test:

enter an integer: 10

raised CONSTRAINT_ERROR : buffer_overflow.adb:11 range check failed 
(normal 10*2*10^9 = too big for 32 bit int)
[2014-05-14 20:55:07] process exited with status 1 (elapsed time: 01.51s)

Thanks

Laurent

with Ada.Text_IO;
with Ada.Integer_Text_IO;

procedure Test_Fibonacci is
   N : Positive;
   Result : Positive := 1;
   Buffer_Overflow : exception;

   function Fibonacci_Iter (N : in Positive) return Positive is
   -- Returns the Nth Fibonacci number, computed iteratively
   -- Pre : N is defined and N >= 1
   -- Post: returns N!

      First : Positive := 1;
      Second : Positive := 1;

   begin -- Fibonacci Iteration

      if N = 1 or N = 2 then
         return Result;
      else
         for Count in 3 .. N loop
            Result := First + Second;
            First := Second;
            Second := Result;
         end loop;
         if Result'Valid then            
            return Result;
         else
            raise Buffer_Overflow;
         end if;            
      end if;
   end Fibonacci_Iter;
   
   function Fibonacci_Rec (N : in Positive) return Positive is
   -- Returns the Nth Fibonacci number, computed recursively
   -- Pre : N is defined and N >= 1
   -- Post: returns N!
  
   begin  -- Fibonacci Recursion

      if (N = 1) or (N = 2) then
         return 1;
      else
         return Fibonacci_Rec (N - 2) + Fibonacci_Rec (N - 1);        
      end if;
   end Fibonacci_Rec;

begin -- Test Fibonacci

   Ada.Text_IO.Put (Item => "Please enter an integer (>0) > ");
   Ada.Integer_Text_IO.Get (Item => N);
   Ada.Text_IO.New_Line;
   Ada.Text_IO.Put (Item => "The fibonacci sequence for N ="
                    & Positive'Image (N) & " is: " );
   Ada.Text_IO.New_Line;

   for Count in 1..N loop
      --Ada.Integer_Text_IO.Put (Item => Fibonacci_Iter (N => Count), Width => 1);
      Ada.Integer_Text_IO.Put (Item => Fibonacci_Rec (N => Count), Width => 1);
      Ada.Text_IO.New_Line;
      --Ada.Text_IO.Put(Item => ' ');
   end loop;

   end Test_Fibonacci;

-----------------------------

with Ada.Integer_Text_IO;
with Ada.Text_IO;

procedure Buffer_Overflow is
   Result : Positive;
   N      : Positive;

begin
   Ada.Text_IO.Put (Item => "enter an integer: ");
   Ada.Integer_Text_IO.Get(Item => N);
   Result := N * 2_000_000_000;
   Ada.Integer_Text_IO.Put (Item => Result, Width => 1);
end Buffer_Overflow;