Computing GCDs over the Gaussian Integers - Revision history

Pgadey at 19:56, 26 November 2011

2011-11-26T19:56:52Z

← Older revision		Revision as of 15:56, 26 November 2011
Line 1:		Line 1:
	I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however:		I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however:

		⚫	''Claim'': <math>\mathbb{Z}[i]</math> is a Euclidean domain, and hence a PID, and hence a UFD.<br />

⚫	''Claim'': <math>\ZZ[i]</math> is a Euclidean domain, and hence a PID, and hence a UFD.<br />

		⚫	Consider the norm function <math>\nu(a + bi) = a^2 + b^2</math>. We write the standard norm on the complex plane as <math>\|\|a+bi\|\|_{\mathbb{C}} = \sqrt{a^2 + b^2}</math>. We show that for all <math>x \neq 0</math> and <math>y</math> we have, <math> y = qx + r </math> where <math>\nu(r) = 0</math> or <math>\nu(r) < \nu(x)</math>. Consider <math>x</math> and <math>y</math> as points on the complex plane. Since <math>x \neq 0</math> we have that <math>y/x</math> is another point in the complex plane. Consider <math>\mathbb{Z}[i]</math> as the points with integer coordinates in <math>\mathbb{C}</math>. For any point <math>\zeta \in \mathbb{C}</math> we can find a <math>\zeta' \in \mathbb{Z}[i]</math> such that <math>\|\|\zeta - \zeta'\|\|_{\mathbb{C}} \leq \sqrt{2}/2</math> by taking the <math>\zeta'</math> to be the nearest lattice point to <math>\zeta</math>. Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take <math>z</math> to be the nearest lattice point to <math>y/x</math>. We then have <math>y = zx + (y - zx)</math>. We compute the norm of <math>\nu(y - zx)</math>. We have: <math> \sqrt{\nu(y - zx)} = \|\|y - zx\|\|_{\mathbb{C}} = \|\|x\|\|_{\mathbb{C}} \cdot \|\|y/x - z\|\|_{\mathbb{C}} \leq \|\|x\|\|_{\mathbb{C}} \frac{\sqrt{2}}{2} < \|\|x\|\|_{\mathbb{C}} = \sqrt{\nu(x)} </math> It follows that <math>\nu(y - zy) < \nu(x)</math>. We obtain that <math>\mathbb{Z}[i]</math> is a Euclidean domain. Thus <math>\mathbb{Z}[i]</math> is a PID and hence a UFD by results given in class.

⚫	Consider the norm function <math>\nu(a + bi) = a^2 + b^2</math>. We write the standard norm on the complex plane as <math>\|\|a+bi\|\|_{\mathbb{C}} = \sqrt{a^2 + b^2}</math>. We show that for all <math>x \neq 0</math> and <math>y</math> we have, <math> y = qx + r </math> where <math>\nu(r) = 0</math> or <math>\nu(r) < \nu(x)</math>. Consider <math>x</math> and <math>y</math> as points on the complex plane. Since <math>x \neq 0</math> we have that <math>y/x</math> is another point in the complex plane. Consider <math>\ZZ[i]</math> as the points with integer coordinates in <math>\mathbb{C}</math>. For any point <math>\zeta \in \mathbb{C}</math> we can find a <math>\zeta' \in \ZZ[i]</math> such that <math>\|\|\zeta - \zeta'\|\|_{\mathbb{C}} \leq \sqrt{2}/2</math> by taking the <math>\zeta'</math> to be the nearest lattice point to <math>\zeta</math>. Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take <math>z</math> to be the nearest lattice point to <math>y/x</math>. We then have <math>y = zx + (y - zx)</math>. We compute the norm of <math>\nu(y - zx)</math>. We have: <math> \sqrt{\nu(y - zx)} = \|\|y - zx\|\|_{\mathbb{C}} = \|\|x\|\|_{\mathbb{C}} \cdot \|\|y/x - z\|\|_{\mathbb{C}} \leq \|\|x\|\|_{\mathbb{C}} \frac{\sqrt{2}}{2} < \|\|x\|\|_{\mathbb{C}} = \sqrt{\nu(x)} </math> It follows that <math>\nu(y - zy) < \nu(x)</math>. We obtain that <math>\ZZ[i]</math> is a Euclidean domain. Thus <math>\ZZ[i]</math> is a PID and hence a UFD by results given in class.

Pgadey at 19:55, 26 November 2011

2011-11-26T19:55:55Z

← Older revision		Revision as of 15:55, 26 November 2011
Line 1:		Line 1:
	I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness.		I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however:


			''Claim'': <math>\ZZ[i]</math> is a Euclidean domain, and hence a PID, and hence a UFD.<br />


			Consider the norm function <math>\nu(a + bi) = a^2 + b^2</math>. We write the standard norm on the complex plane as <math>\|\|a+bi\|\|_{\mathbb{C}} = \sqrt{a^2 + b^2}</math>. We show that for all <math>x \neq 0</math> and <math>y</math> we have, <math> y = qx + r </math> where <math>\nu(r) = 0</math> or <math>\nu(r) < \nu(x)</math>. Consider <math>x</math> and <math>y</math> as points on the complex plane. Since <math>x \neq 0</math> we have that <math>y/x</math> is another point in the complex plane. Consider <math>\ZZ[i]</math> as the points with integer coordinates in <math>\mathbb{C}</math>. For any point <math>\zeta \in \mathbb{C}</math> we can find a <math>\zeta' \in \ZZ[i]</math> such that <math>\|\|\zeta - \zeta'\|\|_{\mathbb{C}} \leq \sqrt{2}/2</math> by taking the <math>\zeta'</math> to be the nearest lattice point to <math>\zeta</math>. Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take <math>z</math> to be the nearest lattice point to <math>y/x</math>. We then have <math>y = zx + (y - zx)</math>. We compute the norm of <math>\nu(y - zx)</math>. We have: <math> \sqrt{\nu(y - zx)} = \|\|y - zx\|\|_{\mathbb{C}} = \|\|x\|\|_{\mathbb{C}} \cdot \|\|y/x - z\|\|_{\mathbb{C}} \leq \|\|x\|\|_{\mathbb{C}} \frac{\sqrt{2}}{2} < \|\|x\|\|_{\mathbb{C}} = \sqrt{\nu(x)} </math> It follows that <math>\nu(y - zy) < \nu(x)</math>. We obtain that <math>\ZZ[i]</math> is a Euclidean domain. Thus <math>\ZZ[i]</math> is a PID and hence a UFD by results given in class.



	----		----

Pgadey at 19:47, 26 November 2011

2011-11-26T19:47:46Z

← Older revision		Revision as of 15:47, 26 November 2011
Line 1:		Line 1:
	I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee.		I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness.

	----		----

Pgadey at 19:46, 26 November 2011

2011-11-26T19:46:11Z

← Older revision		Revision as of 15:46, 26 November 2011
Line 3:		Line 3:
	----		----

			<pre>

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

	&gcd($z1, $z2);		&gcd($z1, $z2);

			</pre>

Pgadey at 19:45, 26 November 2011

2011-11-26T19:45:52Z

New page

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