#!/usr/bin/perl
use CGI qw(param);
# Compute gcf(a, b) as linear combination of a and b
print "Content-type: text/html\n\n";
print "Output
\n";
my $a = param("inputa");
my $b = param("inputb");
$a=int($a);
$b=int($b);
$nit=1;
$sa=1;
$sb=1;
if($a<0){$sa=-1;}
if($b<0){$sb=-1;}
$x=$a;
$y=$b;
$a=$sa*$a;
$b=$sb*$b;
if($a > 10000000 || $b > 10000000){print "Error: |a| and |b| must be integers no bigger than 10,000,000. Try again.
\n";} else
{
if($a+$b==0){print "a=0, b=0; gcf(a, b) is undefined
\n";} else {
if($a==0){print "a=0, b=$y; gcf(a, b) = $b; 0*a + $sb*b = $b
\n";} else {
if($b==0){print "a=$x, b=0; gcf(a, b) = $a; $sa*a + 0*b = $a
\n";} else {
# print "$a, $b\n";
$r = $a%$b;
$c0=0;
$c1=1;
while($r>0){
$nit=$nit+1;
$a=$b;
$b=$r;
$r=$a%$b;
$q=int($a/$b)-1;
while($q*$b+$r<$a){$q=$q+1;}
$c=$c0-$c1*$q;
$c0=$c1;
$c1=$c;
# print "... $a, $b, $r, $c\n";
}
$d = int(($b - $c0*$sa*$x)/($sb*$y));
$s = $d*$sb*$y + $c0*$sa*$x;
$c0=$sa*$c0;
$d=$sb*$d;
print " a=$x, b=$y
\n gcf(a, b) = $b
\n $c0*a + $d*b = gcf(a, b)
Number of iterations = $nit\n";
}}}}
print "\n";