View source for 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. 

----


#!/usr/bin/perl
use Math::Complex;

## 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);