Bézout's identity, finding integers x and y such that ax by = gcd(a,b)-CodePudding

The gcd function in the following code is given in the book Programming Challenges by Steven Skiena as a way of finding integers x and y such that ax by = gcd(a,b). For example, given that a = 34398 and b = 2132 (whose gcd = 26), the algorithm the code below is meant to execute should return 34398 × 15 2132 × −242 = 26. The algorithm to find x and y is based on the base case y = 1 and x = 0 since a * 1 0*0 = gcd(a,0) and according to Euclid's algorithm gcd(34398, 2132) reduces to gcd(gcd(34398, 2132),0) or gcd(26,0). Euclid's algorithm can be applied backwards to find that 34398 × 15 2132 × −242 = 26.

#include <stdio.h>
#include <math.h>

int main() { 
    gcd(34398, 2132, 0, 1);

    /* Find the gcd(p,q) and x,y such that p*x   q*y = gcd(p,q) */
    long gcd(long p, long q, long *x, long *y)
    {
        long x1,y1; /* previous coefficients */
        long g; /* value of gcd(p, q) */

        if (q > p) return(gcd(q, p, y, x));

        if (q == 0) {
            *x = 1;
            *y = 0;
            return(p);
        }

        g = gcd(q, p % q, &x1, &y1);
        *x = y1;
        *y = (x1 - floor(p / q) * y1);
        return(g);
    }

    return 0;
}

How do you test this code? The required input seems to be the p, q, and the base case x and y values but when I run the program below using the line of code gcd(34398, 2132, 0, 1); there is a runtime error message that states 'conflicting types for gcd'.

CodePudding user response：

The declaration long gcd(long p, long q, long *x, long *y) says the last two parameters of gcd are pointers. So you must pass it pointers to existing long; you cannot pass it values such as 0 and 1.

To do that, define two long objects in main, possibly also called x and y, such as long x = 0, y = 1;. Then pass pointers to those objects to gcd, as with gcd(34398, 2132, &x, &y);.

Further, you must put the declaration of gcd before any use of it.

Defining gcd inside main is an extension to the C standard. That extension is useful in situations where the nested function needs certain context from its containing function. There is no need for that here, so the function should be defined in the ordinary way. Move the entire definition of gcd from inside main to before main.

There is no reason to use floor in floor(p / q), because p and q have integer type and integer division will be performed. There will be no fraction part for floor to remove. It can actually make the result wrong if the double type has less precision than the long type. So just use p/q.

There is also no reason to use recursion in this code. It is wasteful and not pedagogical in this situation. (Referring to the book Programming Challenges, the author says “Euclid’s algorithm is recursive…” However, I have a 2003 English translation of Euclid’s Elements, circa 300 BCE. Looking at Euclid’s GCD algorithm in Book VII, Propositions 1 and 2, I would say it is iterative, not recursive. In its cumbersome way, as seen through modern eyes, it describes doing things repeatedly, not reapplying the whole algorithm de novo.)