cubbi.com: fibonacci numbers in perl
Perl
Date: 1987
Type: Imperative scripting language
Usage: Text processing and scripting

ALGORITHM 1A: NAIVE BINARY RECURSION
# This program calculates the nth fibonacci number
# using alrogirhtm 1A: naive binary recursion
#
# compiled: n/a
# executed perl f1a.pl n
#

# Naive binary recursion: F(n) = F(n-1) + F(n-2)
sub fib {
    return @_[0] < 2 ? @_[0] : fib(@_[0]-1) + fib(@_[0]-2)
}

# Subroutine f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
sub f {
    if (@_[0] < 0) {
        return @_[0] % 2 ? fib(-@_[0]) : -fib(-@_[0]);
    } else {
        return fib(@_[0]);
    }
}

# Subroutine fib_print(n) prints out nth Fibonacci number
sub fib_print {
	print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}

# entry point: check the number of command line parameters and check that
# the first parameter is an integer, if either fails, report usage information 
if ( $#ARGV || int($ARGV[0]) ne $ARGV[0]) {
    die "Usage: perl ", $0, " <n>\n";
} else {
   fib_print($ARGV[0]);
}

ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
#!/usr/bin/perl
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 2A-3 - DATA STRUCTURE - SIMPLE LIST
sub f {
  @fl=(new Math::BigInt("1"),new Math::BigInt("1"));
  $fl[$i+1]=$fl[$i-1]+$fl[$i] until $i++==@_[0];
  return $fl[@_[0]]
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
	print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(500);

ALGORITHM 2B: SIMPLE RECURSION
#!/usr/bin/perl
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 2B - SIMPLE RECURSION
sub f {
  return l(new Math::BigInt("1"), new Math::BigInt("1"), @_[0])
}
sub l {
  return @_[2] < 2 ? @_[0] : l(@_[0]+@_[1], @_[0], @_[2]-1);
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
    print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(500);

ALGORITHM 2C: NON-RECURSIVE LOOP
#!/usr/bin/perl
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 2C - NON-RECURSIVE LOOP
sub f {
  $x1=new Math::BigInt "1";
  $x2=new Math::BigInt "1";
  $tmp=new Math::BigInt "0";
  for(;$i < @_[0]; $i++) {
     $tmp=$x1+$x2; $x1=$x2; $x2=$tmp;
  }
  return $x1;
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
   print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(500);

ALGORITHM 3A: MATRIX EQUATION
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 3A - MATRIX EQUATION
sub f {
    @a=(new Math::BigInt("1"),new Math::BigInt("1"),
        new Math::BigInt("1"),new Math::BigInt("0"));
    @b=mp(@a,@_[0]);
    return $b[0];
}                               
# Subroutine mp(@m,$n) raises matrix m into n'th power
sub mp {
    my @a = (@_[0], @_[1], @_[2], @_[3]);
    my $n = @_[4];
    return @a if ($n<2);
    @b=mp(@a,$n / 2);
    return $n%2 ? mm(mm(@b,@b),@a) : mm(@b,@b);
}
# Subroutine mm(@m1,@m2) returns matrix product of m1 and m2
# Where m1 and m2 are 2x2 matrices represented as 4-elementl lists
sub mm {
    my @a = (@_[0], @_[1], @_[2], @_[3]);
    my @b = (@_[4], @_[5], @_[6], @_[7]);
    $d[0]=$a[0]*$b[0]+$a[1]*$b[2];
    $d[1]=$a[0]*$b[1]+$a[1]*$b[3];
    $d[2]=$a[2]*$b[0]+$a[3]*$b[2];
    $d[3]=$a[2]*$b[1]+$a[3]*$b[3];
    return @d;
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
	print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(50000);

ALGORITHM 3B: FAST RECURSION
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 3B - FAST RECURSION
sub f {
    my @a=l(@_[0]);
    return $a[0];
}
sub l {
    return (new Math::BigInt("1"),new Math::BigInt("1")) if @_[0]<=1;
    return (new Math::BigInt("2"),new Math::BigInt("1")) if @_[0]==2;
    if (@_[0] % 2) {
        my @k = l((@_[0]-1)/2);
        return ($k[0]*($k[0]+$k[1]) + $k[0]*$k[1],
                $k[0]*$k[0] + $k[1]*$k[1]);
    } else {
        my @k = l((@_[0]/2)-1);
        return (($k[0]+$k[1])*($k[0]+$k[1]) + $k[0]*$k[0],
                ($k[0]+$k[1])*$k[0] + $k[0]*$k[1]);
    }
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
	print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(50000);

ALGORITHM 3C: BINET'S FORMULA
#!/usr/bin/perl
use Math::BigInt;
# Subroutine f(n) returns nth Fibonacci number
# It uses ALGORITHM 3C - BINET'S FORMULA
sub f {
    $phi = (1+sqrt(5))/2; 
    return ($phi**(@_[0]+1)-(1-$phi)**(@_[0]+1))/sqrt(5);
}
# Subroutine f_print(n) prints out nth Fibonacci number
sub f_print {
    print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
f_print(69);