#!perl -w

use strict;

use Bit::Vector;

print "1..693\n";

my $n = 1;

my $x = Bit::Vector->new(128);
my $y = Bit::Vector->new(128);
my $z = Bit::Vector->new(128);

my $u = Bit::Vector->new(128);
my $v = Bit::Vector->new(128);
my $w = Bit::Vector->new(128);

my($uu,$vv,$ww,$xx,$yy,$zz);

sub gcd($$$$$)
{
    my($a,$b,$c,$d,$e) = @_;
    my($q,$r,$i);
    my(@t);

    $t[0] = [ $a, 1, 0, 0 ];
    $t[1] = [ $b, 0, 1, 0 ];

    $x->from_Dec($a);
    $y->from_Dec($b);

#   printf("\n[ %6d, %6d, %6d, %6d ]\n", @{$t[0]});

    $i = 0;

    if ($t[$i][0])
    {
        while ($t[$i+1][0])
        {
            $a = $t[$i][0];
            $b = $t[$i+1][0];
            $q = int( $a / $b );
            $r = $a - $q * $b;
            $t[$i+2][0] = $r;
            $t[$i+2][1] = $t[$i][1] - $t[$i+1][1] * $q;
            $t[$i+2][2] = $t[$i][2] - $t[$i+1][2] * $q;
            $t[$i+1][3] = $q;
#           printf("[ %6d, %6d, %6d, %6d ]\n", @{$t[$i+1]});
            $i++;
        }
    }
    else
    {
        $t[$i][0] = $t[$i+1][0];
        $t[$i][1] = 0;
        $t[$i][2] = 1;
    }

#   printf("[ %6d, %6d, %6d, %6d ]\n", @{$t[$i+1]});

#   print "\nGCD1( $t[0][0], $t[1][0] ) = ", $t[$i][0], "\n";

    if ($t[$i][0] == $c)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#1: $t[$i][0] != $c\n";} # 1
    $n++;

    $z->GCD($x,$y);

    $xx = $x->to_Dec();
    $yy = $y->to_Dec();
    $zz = $z->to_Dec();

#   printf("GCD2( %s, %s ) = %s\n", $xx, $yy, $zz);

    if ($zz == $c)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#2: $zz != $c\n";} # 2
    $n++;

    $z->GCD($v,$w,$x,$y);

    $xx = $x->to_Dec();
    $yy = $y->to_Dec();
    $zz = $z->to_Dec();

    $vv = $v->to_Dec();
    $ww = $w->to_Dec();

#   printf("GCD3( %s, %s ) = %s\n", $xx, $yy, $zz);

    if ($zz == $c)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#3: $zz != $c\n";} # 3
    $n++;

    $v->Multiply($v,$x);
    $w->Multiply($w,$y);
    $u->add($v,$w,0);

    $uu = $u->to_Dec();

#   printf("\n%d * %d + %d * %d = %d\n",
#       $t[$i][1],  $t[0][0],
#       $t[$i][2],  $t[1][0],
#       $t[$i][1] * $t[0][0] +
#       $t[$i][2] * $t[1][0]);

    if (($t[$i][1] * $t[0][0] + $t[$i][2] * $t[1][0]) == $c)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#4: $t[$i][1] * $t[0][0] + $t[$i][2] * $t[1][0] != $c\n";} # 4
    $n++;

    if ($t[$i][1] == $d)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#5: $t[$i][1] != $d\n";} # 5
    $n++;

    if ($t[$i][2] == $e)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#6: $t[$i][2] != $e\n";} # 6
    $n++;

#   printf("%s * %s + %s * %s = %s\n\n", $vv, $xx, $ww, $yy, $uu);

    if ($uu == $c)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#7: $uu != $c\n";} # 7
    $n++;

    if ($vv == $d)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#8: $vv != $d\n";} # 8
    $n++;

    if ($ww == $e)
    {print "ok $n\n";} else {print "not ok $n\n";warn "#9: $ww != $e\n";} # 9
    $n++;
}

gcd(      0,      0,      0,      0,      1 );

gcd(      0,      1,      1,      0,      1 );
gcd(      1,      0,      1,      1,      0 );
gcd(      0,     -1,     -1,      0,      1 );
gcd(     -1,      0,     -1,      1,      0 );

gcd(      0,      2,      2,      0,      1 );
gcd(      2,      0,      2,      1,      0 );
gcd(      0,     -2,     -2,      0,      1 );
gcd(     -2,      0,     -2,      1,      0 );

gcd(      0,      3,      3,      0,      1 );
gcd(      3,      0,      3,      1,      0 );
gcd(      0,     -3,     -3,      0,      1 );
gcd(     -3,      0,     -3,      1,      0 );

gcd(      1,      1,      1,      0,      1 );
gcd(      1,     -1,     -1,      0,      1 );
gcd(     -1,      1,      1,      0,      1 );
gcd(     -1,     -1,     -1,      0,      1 );

gcd(      1,      2,      1,      1,      0 );
gcd(      2,      1,      1,      0,      1 );
gcd(     -1,      2,     -1,      1,      0 );
gcd(      2,     -1,     -1,      0,      1 );
gcd(      1,     -2,      1,      1,      0 );
gcd(     -2,      1,      1,      0,      1 );
gcd(     -1,     -2,     -1,      1,      0 );
gcd(     -2,     -1,     -1,      0,      1 );

gcd(      2,      3,      1,     -1,      1 );
gcd(      3,      2,      1,      1,     -1 );
gcd(     -2,      3,      1,      1,      1 );
gcd(      3,     -2,      1,      1,      1 );
gcd(      2,     -3,     -1,      1,      1 );
gcd(     -3,      2,     -1,      1,      1 );
gcd(     -2,     -3,     -1,     -1,      1 );
gcd(     -3,     -2,     -1,      1,     -1 );

gcd(      3,      5,      1,      2,     -1 );
gcd(      5,      3,      1,     -1,      2 );
gcd(     -3,      5,     -1,      2,      1 );
gcd(      5,     -3,     -1,      1,      2 );
gcd(      3,     -5,      1,      2,      1 );
gcd(     -5,      3,      1,      1,      2 );
gcd(     -3,     -5,     -1,      2,     -1 );
gcd(     -5,     -3,     -1,     -1,      2 );

gcd(      5,      7,      1,      3,     -2 );
gcd(      7,      5,      1,     -2,      3 );
gcd(     -5,      7,     -1,      3,      2 );
gcd(      7,     -5,     -1,      2,      3 );
gcd(      5,     -7,      1,      3,      2 );
gcd(     -7,      5,      1,      2,      3 );
gcd(     -5,     -7,     -1,      3,     -2 );
gcd(     -7,     -5,     -1,     -2,      3 );

gcd(      6,     30,      6,      1,      0 );
gcd(     30,      6,      6,      0,      1 );
gcd(     -6,     30,     -6,      1,      0 );
gcd(     30,     -6,     -6,      0,      1 );
gcd(      6,    -30,      6,      1,      0 );
gcd(    -30,      6,      6,      0,      1 );
gcd(     -6,    -30,     -6,      1,      0 );
gcd(    -30,     -6,     -6,      0,      1 );

gcd(   2322,      0,   2322,      1,      0 );
gcd(      0,    654,    654,      0,      1 );
gcd(  -2322,      0,  -2322,      1,      0 );
gcd(      0,   -654,   -654,      0,      1 );

gcd(   2322,    654,      6,     20,    -71 );
gcd(   2322,   -654,      6,     20,     71 );
gcd(  -2322,    654,     -6,     20,     71 );
gcd(  -2322,   -654,     -6,     20,    -71 );
gcd(    654,   2322,      6,    -71,     20 );
gcd(    654,  -2322,     -6,     71,     20 );
gcd(   -654,   2322,      6,     71,     20 );
gcd(   -654,  -2322,     -6,    -71,     20 );

gcd(  12345,  54321,      3,   3617,   -822 );
gcd(  12345, -54321,      3,   3617,    822 );
gcd( -12345,  54321,     -3,   3617,    822 );
gcd( -12345, -54321,     -3,   3617,   -822 );
gcd(  54321,  12345,      3,   -822,   3617 );
gcd(  54321, -12345,     -3,    822,   3617 );
gcd( -54321,  12345,      3,    822,   3617 );
gcd( -54321, -12345,     -3,   -822,   3617 );

__END__