Computing GCDs over the Gaussian Integers

I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee.

---

1. !/usr/bin/perl

use Math::Complex;

1. 1. A Quick hack for computing GCDs of Gaussian integers.

$z2 = 857 + i; $z1 = 255;

sub gcd { # the Euclidean algorithm

my $x = $_[0]; my $y = $_[1];

if ($x * $y == 0) { print "Done!\n"; } else { $q = &approx($x/$y); $r = $x - $q*$y; print "($x) = ($q)($y) + ($r)\n";

&gcd($y,$r); } }

sub approx { # find the nearest Gaussian integer to a point on the complex plane

my $z = $_[0];

my $x = int(Re($z)); my $y = int(Im($z));

if (abs($z - (($x+1) + i*$y) ) < 1/sqrt(2)) { return ($x+1) + i*$y; } elsif (abs($z - (($x) + i*($y+1)) ) < 1/sqrt(2)) { return $x + i*($y+1); } elsif (abs($z - (($x+1) + i*($y+1)) ) < 1/sqrt(2)) { return ($x+1) + i*($y+1); } else { return $x + i*$y; }

}

&gcd($z1, $z2);