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
- create a new class/struct as a container for two or three numbers
- use two global arrays for m and n and a static counter : each call to the function gets an index location in each array
- dynamically allocate an array of two integers, store the right values
and return the head of the array as a pointer
- store or "concatenate" m,n into a bigger value v= m+ RANGE*n, (assume m,n<RANGE) and return this composed value v.