CS1500 Algorithms and Data Structures for Engineering, FALL 2012

 LAB 4: Euclid's GCD algorithm, coefficients finding, recursion

Write a program that takes two positive (non-zero) integers a an b as inputs and computes their GCD (greatest common divisor) using Euclid’s algorithm. A description of the algorithm can be found here.
You have to also find integers m and n such that a*m + b*n = GCD(a,b).

Recursion: the idea is to have a recursive function that returns two values:  the m and n, then compute the GCD using them and the formula above. When the call terminates, you have to manipulate the returned m and n to compute the "new" m and n (see GCD slides for details).

HINT: To return two values you have to be a bit creative. You can do one of the following:
For this concatenation to work, you need to store m and n as positive values, but they can be negative sometimes; a simple idea is to add on offset (only for the purpose of storage): store m+OFFSET, n+OFFSET into v=m+OFFSET + (n+OFFSET)*RANGE. Further you have to decode v appropriately: get positive values stored, then subtract the offset. Finally OFFSET should cover  the  possible values for m and n; and RANGE>= 2*OFFSET : you can use something like OFFSET=2048 and RANGE=4096