Skip to content

Instantly share code, notes, and snippets.

@tueda
Created September 23, 2013 12:49
Show Gist options
  • Save tueda/6669948 to your computer and use it in GitHub Desktop.
Save tueda/6669948 to your computer and use it in GitHub Desktop.
An implementation of the extended euclidean algorithm.
**
* The extended euclidean algorithm, which gives x and y such that
* a*x + b*y = gcd(a, b) >= 0.
* Input: Integers $a and $b.
* Output: Integers $x and $y.
*
#procedure ExtGCD(a,b,x,y,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6)
#define aa "`tmp1'"
#define bb "`tmp2'"
#define lastx "`tmp3'"
#define lasty "`tmp4'"
#define q "`tmp5'"
#define tmp "`tmp6'"
$`aa' = abs_($`a');
$`bb' = abs_($`b');
$`x' = 0;
$`y' = 1;
$`lastx' = 1;
$`lasty' = 0;
$`tmp' = termsin_($`bb');
while ($`tmp');
$`q' = integer_($`aa'/$`bb');
$`tmp' = $`bb';
if ($`bb' == 1);
$`bb' = 0; * a workaround of mod_(n?,1).
else;
$`bb' = mod_($`aa',$`bb');
endif;
$`aa' = $`tmp';
$`tmp' = $`x';
$`x' = $`lastx' - $`q'*$`x';
$`lastx' = $`tmp';
$`tmp' = $`y';
$`y' = $`lasty' - $`q'*$`y';
$`lasty' = $`tmp';
$`tmp' = termsin_($`bb');
endwhile;
$`x' = sig_($`a')*$`lastx';
$`y' = sig_($`b')*$`lasty';
#endprocedure
* Test
#$a = 244309253330115;
#$b = -222043931593200;
#$dummy = 1;
#inside $dummy
#call ExtGCD(a,b,x,y,tmp1,...,tmp6)
#endinside
L F = dum_($a,$b,$x,$y,$a*$x+$b*$y,abs_(gcd_($a,$b)));
Format nospaces;
P;
.end
* The answer must be (244309253330115,-222043931593200,2243768619423,2468761168673,45,45);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment