#!/usr/bin/perl

# print "gcd(", to_str($p1), ", ", to_str($p2), ") = ", to_str($p3), "\n";


my @polies = ([0], [1], [0, 1], [1, 1], 
              [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1],
              [0, 0, 0, 1], [1, 0, 0, 1], [0, 1, 0, 1], [1, 1, 0, 1],
              [0, 0, 1, 1], [1, 0, 1, 1], [0, 1, 1, 1], [1, 1, 1, 1],
             );

my @polies = map [split //, unpack "b*", pack "s", $_], 0 .. 31;
1;
1;


print "<table cellpadding=0 cellspacing=0 align=center>\n\n";

print "<tr><td colspan=2 style='border-right: black medium solid; border-bottom: black medium solid;'>&nbsp;";
my $letter = "a0";
for my $b (@polies) {
  my $bgcolor = $b->[0] ? "#ffffff" : "#eeeeee";
#  print "<td style='border-bottom: black medium solid; background-color: $bgcolor'>", to_str($b)
  print "<td style='border-bottom: black medium solid;'>", "<tt>$letter</tt>";
  $letter++;
}
print "\n\n";

my $last_row_degree = 0;
my $letter = "a0";
for my $a (@polies) {
  print "<tr><td align=right>", to_str($a), "&nbsp;&nbsp;<td style='border-right: black medium solid;'> [<tt>$letter</tt>] ";
  $letter++;
  my $border_top = $last_row_degree < degree($a) && !is_one($a)
    ? "border-top: black thin solid;" : "";
    
  my $last_col_degree = 0;
  for my $b (@polies) {
    my $border_left = $last_col_degree < degree($b) && !is_one($b)
      ? "border-left: black thin solid;" : "";
#    my $bgcolor = $b->[0] ? "#eeeeee" : "#ffffff";
    my $c = euclid($a, $b);
#    print "<td bgcolor='$bgcolor'>", to_str($c), "  ";
    my $bgcolor = is_one($c) ? "pink" : "white";
    print "<td style='background-color: $bgcolor; $border_top $border_left'>&nbsp;  ";
    $last_col_degree = degree($b);
  }
  print "\n\n";
  $last_row_degree = degree($a);
}
print "</table><p>\n\n";

sub to_str {
  my $a = shift;
  my $n = degree($a);
  return "0" if $n == -1;
  my $first = 1;
  my @terms;
  for my $i (reverse 0 .. $n) {
    next unless $a->[$i];
    push @terms, $i > 1 ? "<i>x</i><sup>$i</sup>" : $i == 1 ? "<i>x</i>" : "1";
  }
  join " + ", @terms;
}

sub is_rp_to {
  my ($a, $b) = @_;
  my $gcd = euclid($a, $b);
  degree($gcd) == 1;
}

sub euclid {
  my ($a, $b) = @_;
  until (is_zero($b)) {
    ($a, $b) = ($b, reduce_by($a, $b));
  }
  return $a;
}

sub reduce_by {
  my ($a, $b) = @_;
  my ($da, $db) = (degree($a), degree($b));
  return $a if $da < $db;
  return add($a, scale($b, $da-$db));
}

sub add {
  my ($a, $b) = @_;
  my @c;
  for my $i (0 .. max(degree($a), degree($b))) {
    push @c, ($a->[$i] + $b->[$i]) % 2;
  }
  return \@c;
}

sub max {
  my ($m, @a) = @_;
  for (@a) {
    $m = $m > $_ ? $m : $_;
  }
  return $m;
}

sub scale {
  my ($a, $n) = @_;
  return [(0) x $n, @$a];
}

# returns -1 for zero polynomial
sub degree {
  my $a = shift;
  pop @$a while @$a && $a->[-1] == 0;
  return $#$a;
}

sub is_zero {
  my $a = shift;
  degree($a) == -1;
}

sub is_one {
  my $a = shift;
  degree($a) == 0;
}