Skip to content

Instantly share code, notes, and snippets.

@ttezel
Created January 25, 2013 17:50
Show Gist options
  • Save ttezel/4636449 to your computer and use it in GitHub Desktop.
Save ttezel/4636449 to your computer and use it in GitHub Desktop.
Extended Euclid Algo for finding the GCD of two integers. Works using Euclid's law: if `d` is the GCD of `a` and `b`, then there exists an `x` and `y` such that ```ax + by = d```
%{
Problem 7 (ii) - Extended Euclid
Input: positive integers a,b with a >= b >= 0
Output: integer array [ x,y,d ] such that
d = gcd(a,b) and ax + by = d
%}
function result = extended_Euclid (a, b)
if (b == 0)
result = [ 1, 0, a ];
return;
end
%M is a matrix of the form [x, y, d ]
M = extended_Euclid(b, mod(a,b));
% result is [ y, x - floor(a/b) * y, d ]
result = [ M(2), M(1) - floor(a/b) * M(2), M(3) ];
return
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment