Fibonacci number program problem

## Program to computes the value of Fibonacci number.

	.text
	.globl  __start

__start:

	sub	$sp,$sp,4	# push return address
	sw	$ra,($sp)
	sub	$sp,$sp,4	# push caller's frame pointer
	sw	$fp,($sp)
	sub	$fp,$sp,8	# $fp = $sp - space_for_variables
	move	$sp,$fp

	li	$v0,4	# call to print string
	la	$a0,pr1
	syscall

	li	$v0,5	# call to read integer
	syscall
	sw	$v0,0($fp)	# save in $v0
	nop

	lw	$a0,0($fp)	# load variable into $a0
	nop
	jal	fib
	nop

	sw	$v0,4($fp)	# b = fib(a)
	nop

	li	$v0,4	# call to print string
	la	$a0,pr2
	syscall

	lw	$a0,4($fp)
	li	$v0,1	# call to print integer
	syscall

	add	$sp,$fp,8	# $sp = $fp + space_for_variables

	lw	$fp,($sp)	# pop $fp
	add	$sp,$sp,4
	lw	$ra,($sp)	# pop $ra
	add	$sp,$sp,4
	jr	$ra	# return to OS
	nop

	.data
pr1:	.asciiz "Enter an interger:"
pr2:	.asciiz "\nThe Fibonacci number is:"

# int Fib( int n )
# {
#   if( n <= 0 )
#      return 0
#   else if( n == 1 )
#       return 1
#   else
#     x = Fib( n-1 )
#     y = Fib( n-2 )
#     return x + y
#   endif
# }

	.text
	.globl  fib

fib:
	sub	$sp,$sp,4	# push return address
	sw	$ra,($sp)
	sub	$sp,$sp,4	# push caller's frame pointer
	sw	$fp,($sp)
	sub	$sp,$sp,4	# push register $s1
	sw	$s1,($sp)
	sub	$fp,$sp,0	# $fp = $sp - space_for_variables (==0)
	move	$sp,$fp

	move	$s1,$a0	# save argument in $s1
	li	$t1,0	# get a==0
	bgt	$s1,$t1,lo1	# if (n <= 0)
	nop
	li	$v0,0	# return 0
	j	exit
	nop

lo1:
	move	$s1,$a0	# save argument in $s1
	li	$t1,1	# get a==1
	beq	$s1,$t1,lo2	# if (n == 1)
	nop
	bgt	$s1,$t1,lo3	# if (n <=1)
	nop

lo2:	li	$v0,1	# return 1
	j	exit
	nop
lo3:	
	sub 	$a0,$s1,1	# param = n-1
	jal 	fib	# compute fib(n-1)
	nop
	move	$v0,$s1	# x = Fib( n-1 )

	sub	$a0,$s1,2	# set param to n-2
	jal 	fib	# and make recursive call
	nop
	add 	$v0,$v0,$s1# add fib(n-2)

exit:
	add	$sp,$fp,0	# $sp = $fp + space_for_variables (==0)
	lw	$s1,($sp)
	add	$sp,$sp,4
	lw	$fp,($sp)	# pop $fp
	add	$sp,$sp,4
	lw	$ra,($sp)	# pop $ra
	add	$sp,$sp,4
	jr	$ra	# return to OS
	nop

(defun fib (n)
  "Naive recursive computation of the nth element of the Fibonacci sequence"
  (check-type n (integer 0 *))
  (if (< n 2) n
      (+ (fib (1- n)) (fib (- n 2)))))

(defun fib (n)
  "do-based iterative computation of the nth element of the Fibonacci sequence"
  (check-type n (integer 0 *))
  (do ((i n (1- i))
       (f1 0 f2)
       (f2 1 (+ f1 f2)))
      ((= i 0) f1)))

         5
     4       3
   3   2    2 1
  2 1   1  1
 1

#include <iostream>
#include <ctime>
int main()
{
	int n;
	std::cout << "Enter a number: ";
	std::cin >> n;
	
	int c = clock();
	int r = f(n);
	c = clock() - c;
	std::cout << "F(" << n << ") is " << r
		<< ", computed using recursion in " << c << " clock cycles.\n";
	system("pause");
}

int f(int n)
{
	if(n == 0 || n == 1) return 1;
	return f(n-1) + f(n-2);
}

int f(int n)
{
	int a[n+1];
	for(int i = 0; i <= n; ++i)
	{
		if(i == 0)
		{
			a[0] = 1;
		}
		else if(i == 1)
		{
			a[1] = 1;
		}
		else
		{
			a[i] = a[i-1] + a[i-2];
		}
	}
	return a[n];
}

n		30		35		40		45		50
----------
fib(n)		1346269		14930352,165580141			-112588406 (overflow)
----------
Clock cycles:
Recursive	15		515	6094		~28150		~130000
Linear		0		0		0

Linear for even n = 100000 shows "0 clock cycles". The integer range has long overflowed it's bounds.

~: I can't run this anymore -- will take minutes and hours, it seems. Recursive f(n) for n = 40 hung my computer for several seconds already. Estimate given.

var phi = (sqrt(5) + 1) / 2;
fib(n) = (phi^n - (1 - phi)^n) / sqrt(5);

Original - Ada Code package Fibo_Tools is subtype Long_Natural is Long_Integer range 0..Long_Integer'Last; type Mod_Natural is mod 2**31; function Fibonacci(N: Natural) return Mod_Natural; end Fibo_Tools;

package Fibo_Tools is
    subtype Long_Natural is Long_Integer range 0..Long_Integer'Last;
    type Mod_Natural is mod 2**31;
 
    function Fibonacci(N: Natural) return Mod_Natural;
end Fibo_Tools; 

Original - Ada Code package body Fibo_Tools is function Fibonacci (N: Long_Natural) return Mod_Natural is begin if (N = 0) then return 0; elsif (N = 1) then return 1; else return Fibonacci(N-1) + Fibonacci(N-2); end if; end Fibonacci; end Fibo_Tools;

package body Fibo_Tools is
    function Fibonacci (N: Long_Natural) return Mod_Natural is
    begin
        if (N = 0) then return 0;
        elsif (N = 1) then return 1;
        else return Fibonacci(N-1) + Fibonacci(N-2);
        end if;
    end Fibonacci;
end Fibo_Tools; 

Original - Ada Code package body Fibo_Tools is function Fibonacci (N: Long_Natural) return Mod_Natural is A: Mod_Natural := 0; B: Mod_Natural := 1; begin for K in 1..N loop B := B + A; A := B - A; end loop; return A; end Fibonacci; end Fibo_Tools;

package body Fibo_Tools is
    function Fibonacci (N: Long_Natural) return Mod_Natural is
        A: Mod_Natural := 0;
        B: Mod_Natural := 1;
    begin
        for K in 1..N loop
            B := B + A;
            A := B - A;
        end loop;
        return A;
    end Fibonacci;
end Fibo_Tools; 

Original - Ada Code package body Fibo_Tools is type Fib_State is array (0..2) of Mod_Natural; procedure Fib_Rec (N: in Long_Natural; X: in out Fib_State) is begin if (N > 0) then Fib_Rec(N/2, X); X(0..2) := (X(0)**2+X(1)**2, X(1)*(X(0)+X(2)), X(1)**2+X(2)**2); if (N mod 2 = 1) then X(0..2) := (X(1), X(2), X(1)+X(2)); end if; end if; end Fib_Rec; function Fibonacci (N: Long_Natural) return Mod_Natural is X: Fib_State := (1, 0, 1); begin Fib_Rec(N, X); return X(1); end Fibonacci; end Fibo_Tools;

package body Fibo_Tools is
    type Fib_State is array (0..2) of Mod_Natural;
 
    procedure Fib_Rec (N: in Long_Natural; X: in out Fib_State) is
    begin
        if (N > 0) then
            Fib_Rec(N/2, X);
            X(0..2) := (X(0)**2+X(1)**2, X(1)*(X(0)+X(2)), X(1)**2+X(2)**2);
            if (N mod 2 = 1) then X(0..2) := (X(1), X(2), X(1)+X(2));
            end if;
        end if;
    end Fib_Rec;
 
    function Fibonacci (N: Long_Natural) return Mod_Natural is
        X: Fib_State := (1, 0, 1);
    begin
        Fib_Rec(N, X);
        return X(1);
    end Fibonacci;
end Fibo_Tools; 

Original - Ada Code with Ada.Text_Io, Ada.Command_Line, Ada.Real_Time, Fibo_Tools; use Fibo_Tools, Ada.Real_Time; procedure Fibo is package Nat_IO is new Ada.Text_IO.Integer_IO(Long_Natural); package Int_IO is new Ada.Text_IO.Integer_IO(Long_Integer); N: Long_Natural; F_N: Mod_Natural; Start_Time: Ada.Real_Time.Time; End_Time: Ada.Real_Time.Time; Ticks: Integer; begin if (Ada.Command_Line.Argument_Count < 1) then Ada.Text_IO.Put_Line( Ada.Text_IO.Standard_Error, "Usage: fibo argument"); return; end if; declare Arg1 : String := Ada.Command_Line.Argument(1); Last : Positive; begin Nat_IO.Get(Arg1, N, Last); end; Start_Time := Ada.Real_Time.Clock; F_N := Fibonacci(N); End_Time := Ada.Real_Time.Clock; -- (using "-", "/" of Ada.Real_Time) Ticks := (End_Time - Start_Time)/Ada.Real_Time.Tick; Int_IO.Put(Long_Integer(F_N), 0); Ada.Text_IO.New_Line(1); Int_IO.Put(Long_Integer(Ticks), 0); Ada.Text_IO.Put(" clock ticks elapsed"); end Fibo;

with Ada.Text_Io, Ada.Command_Line, Ada.Real_Time, Fibo_Tools;
use Fibo_Tools, Ada.Real_Time;
procedure Fibo is
    package Nat_IO is new Ada.Text_IO.Integer_IO(Long_Natural);
    package Int_IO is new Ada.Text_IO.Integer_IO(Long_Integer);
 
    N: Long_Natural;
    F_N: Mod_Natural;
    Start_Time: Ada.Real_Time.Time;
    End_Time: Ada.Real_Time.Time;
    Ticks: Integer;
begin
    if (Ada.Command_Line.Argument_Count < 1) then
        Ada.Text_IO.Put_Line(
            Ada.Text_IO.Standard_Error,
            "Usage: fibo argument");
        return;
    end if;
 
    declare
        Arg1 : String := Ada.Command_Line.Argument(1);
        Last : Positive;
    begin
        Nat_IO.Get(Arg1, N, Last);
    end;
 
    Start_Time := Ada.Real_Time.Clock;
    F_N := Fibonacci(N);
    End_Time := Ada.Real_Time.Clock;
 
    -- (using "-", "/" of Ada.Real_Time)
    Ticks := (End_Time - Start_Time)/Ada.Real_Time.Tick;
 
    Int_IO.Put(Long_Integer(F_N), 0);
    Ada.Text_IO.New_Line(1);
    Int_IO.Put(Long_Integer(Ticks), 0);
    Ada.Text_IO.Put(" clock ticks elapsed");
end Fibo;