CODEWITHSUNDEEP
cpseudocode
Giuseppe
Giuseppe

Reputation: 492

How to change this pseudocode to C syntax

I've found this pseudocode from Wikipedia of Euclid's extended Algorithm, but I don't know how to return 2 values from a function.

function extended_gcd(a, b)
    if b = 0
        return (1, 0)
    else
        (q, r) := divide (a, b)
        (s, t) := extended_gcd(b, r)
        return (t, s - q * t)

Source: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Upvotes: 1

Views: 1130

Answers (3)

BLUEPIXY
BLUEPIXY

Reputation: 40145

#include <stdio.h>

typedef struct _tuple {
    int fst;
    int snd;
} Tuple;

Tuple tuple(int a, int b){
    Tuple ret = { a, b };
    return ret;
}

Tuple extended_gcd(Tuple x){
    if(x.snd == 0)
        return tuple(1,0);
    else {
        Tuple qr = tuple(x.fst/x.snd, x.fst%x.snd);
        Tuple st = extended_gcd(tuple(x.snd, qr.snd));
        return tuple(st.snd, st.fst - qr.fst * st.snd);
    }
}

int main() {
    Tuple ans = extended_gcd(tuple(120,23));
    printf("(%d,%d)\n", ans.fst, ans.snd);//(-9,47)
    return 0;
}

Upvotes: 1

Keith Thompson
Keith Thompson

Reputation: 263357

Your question is tagged both C and C++.

In C, you can't actually return two values from a function, but there are several ways to achieve the same effect.

You can return a struct. See, for example, the div function, declared in <stdlib.h>, which returns a result of type div_t, a struct containing quot and rem members.

Or you can "return" more than one result indirectly, by passing a pointer:

void func(int *result1, int *result2) {
    *result1 = 10;
    *result2 = 20;
}
...
int r1, r2;
func(&r1, &r2);

C++ supports both of these methods, plus a few others. For example, C++ has reference types; there are also types in the C++ standard library, such as std::pair and tuples, that can be used for this kind of thing.

But before you start implementing this, you should decide which language you're using.

Upvotes: 3

Ernest Friedman-Hill
Ernest Friedman-Hill

Reputation: 81694

The template class std::pair could be used for this; i.e.,

if (b == 0)
    return std::pair<int, int>(1, 0);

Upvotes: 2

Related Questions