

sub gcd_r {
  return $_[0] if $_[1] == 0;
  return gcd_r($_[1], $_[0]%$_[1]);
}

sub gcd_i {
  return $_[0] if $_[1] == 0;
  @_ = ($_[1], $_[0]%$_[1]);
  goto &gcd_i;
}

@tests = (12, 6,   60, 18,   100, 70,   10921238, 123871);
# @tests = 
while (@tests) {
  my ($a, $b) = splice @tests, 0, 2;
  my $r = gcd_r($a, $b);
  my $i = gcd_i($a, $b);
  print "Error on gcd($a,$b) = $r ? $i\n" unless $r == $i;
  print "gcd($a,$b) = $r\n";
}

@N = (40320, 1190);
$N = shift || 10000;

$i = $N;
my ($su, $ss) = times;
while ($i--) {
  gcd_r(@N);
}
my ($eu, $es) = times;
my ($tu, $ts) = ($eu-$su, $es-$ss);
my $t = $tu+$ts;
print "gcd_r: u$tu s$ts t:$t\n";

$i = $N;
my ($su, $ss) = times;
while ($i--) {
  gcd_i(@N);
}
my ($eu, $es) = times;
my ($tu, $ts) = ($eu-$su, $es-$ss);
my $t = $tu+$ts;
print "gcd_i: u$tu s$ts t:$t\n";
