Cheap, Fast, Good - Common Factor (Greatest) Inspired by Cheap, Fast, Good, we're going to implement an algorithm which has exactly two of them.

The Math

Given two nonzero integers a and b, the GCF d is the largest integer that divides both a and b without remainder. Bézout coefficients are pairs of integers (x, y) such that ax + by = d. Bézout coefficients are not unique. For example, given:

a = 15, b = 9


We have

d =  3
x =  2
y = -3


Since 15*2 + 9*(-3) = 30 - 27 = 3.

A common way to calculate the GCF and a pair of Bézout coefficients is using Euclid's Algorithm, but it's by no means the only way.   

The Code

Your program should take two integers as inputs. It should output/return the greatest common factor and one pair of Bézout coefficients.

Example input:

15 9


example output

3 (2, -3)


The output can be in any order and format, but it should be clear which is the GCF and which are the coefficients.

The Underhanded

Your program has the potential to be cheap, fast, and good. Unfortunately, it can only be two of those at once.


When it's not cheap, the program should use an excessive amount of system resources.
When it's not fast, the program should take an excessive amount of time.
When it's not good, the program output should be wrong.


The program should be able to do (well, not do) all three. Which is does when is up to you- it could be based on the time, the compiler, which input is larger, etc. Some additional notes:


Your program should not be obviously underhanded and should pass a cursory inspection. I'd be a little suspicious if you implemented three separate algorithms.
In the cheap case, "excessive amount of system resources" is anything that would slow down other programs. It could be memory, bandwidth, etc.
In the fast case, "excessive time" means relative to how it runs in the cheap and good cases. The program should still finish. The closer you can to "incredibly frustrating but not frustrating enough to stop the program" the (funnier and) better.
In the good case, the output shouldn't be obviously wrong  and should pass a cursory inspection. I'd be very suspicious if it gave me a GCF of "2 anna half".


This is a popularity contest, so most upvotes wins!

EDIT

To clarify, I'm looking for programs that can be "fast and cheap" and "cheap and good" and "fast and good" in different cases, not ones that just do one of them.
C
It's cheap and fast. You get gcd in the blink of an eye. However the guy who did it had no clue about that &quot;Bézier co-something&quot; so he simply divided a and b by gcd.
(to make things worse, at that point a and b are pretty far from their initial value because of the algorithm he wisely chose)
int main(int argc, char **argv){
    unsigned int a, b, tmp;
    a = (unsigned int)atoi(argv[1]);
    b = (unsigned int)atoi(argv[2]);
    for (tmp = 0; ((a | b) & 1) == 0; ++tmp){
        a &gt;&gt;= 1;
        b &gt;&gt;= 1;
    }
    while ((a & 1) == 0) 
        a &gt;&gt;= 1;
    do {
        while ((b & 1) == 0)
            b &gt;&gt;= 1;
        if (a &gt; b){
            unsigned int t = b; 
            b = a; 
            a = t;
        }  
        b = b - a;
    } while (b != 0);
    tmp = a &lt;&lt; tmp;
    printf("%u, (%u,%u)", tmp, a/tmp, b/tmp);
    return 0;
}