serious stuff
www.cubbi.com
personal
programming
fibonacci numbers
algorithms
benchmarks
forth examples
postscript examples
muf examples
joy examples
j examples
scheme examples
hope examples
ocaml examples
haskell examples
prolog examples
c++ examples
java examples
assembly language examples
fortran examples
c examples
sh examples
awk examples
perl examples
tcl examples
asmix
hacker test
resume
science
martial arts
fun stuff
www.cubbi.org
|
Perl
Date: 1987
Type: Imperative scripting language
Usage: Text processing and scripting
ALGORITHM 1A: NAIVE BINARY RECURSION |
sub fib {
return @_[0] < 2 ? @_[0] : fib(@_[0]-1) + fib(@_[0]-2)
}
sub f {
if (@_[0] < 0) {
return @_[0] % 2 ? fib(-@_[0]) : -fib(-@_[0]);
} else {
return fib(@_[0]);
}
}
sub fib_print {
print @_[0], "th Fibonacci number is ", f(@_[0]), "\n";
}
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);
|
|