use Math::BigInt;
use Benchmark;
use strict;
$|++;

my $t0;
my $t1;
my $i = Math::BigInt->new($ARGV[0]);

$t0 = new Benchmark;
fact($i);
$t1 = new Benchmark;
print "Method 1: ",timestr(timediff($t1, $t0)),"\n";

$t0 = new Benchmark;
fact2($i,1);
$t1 = new Benchmark;
print "Method 2: ",timestr(timediff($t1, $t0)),"\n";

$t0 = new Benchmark;
fact3($i);
$t1 = new Benchmark;
print "Method 3: ",timestr(timediff($t1, $t0)),"\n";

sub fact{
  my $n = Math::BigInt->new(shift);
  return 1 unless $n->bcmp(0);
  return $n->bmul(fact($n->bsub(1)));
}

sub fact2{
  #Tail Recursion Ellimination
  my $n = Math::BigInt->new(shift);
  my $f = shift;
  if (!$n->bcmp(0)) {return $f}
  else {return &fact2($n->bsub(1),$n->bmul($f))}
}

sub fact3{
  #no recursion at all
  my $n = Math::BigInt->new($_[0]);
  my $i = $_[0]-1;
  while($i){
    $n = Math::BigInt->new($n->bmul($i--));
  }
  return $n;
}