Cheap, Fast, Good - Common Factor (Greatest)

Question

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.

Answer 1

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 "Bézier co-something" 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 >>= 1;
        b >>= 1;
    }
    while ((a & 1) == 0) 
        a >>= 1;
    do {
        while ((b & 1) == 0)
            b >>= 1;
        if (a > b){
            unsigned int t = b; 
            b = a; 
            a = t;
        }  
        b = b - a;
    } while (b != 0);
    tmp = a << tmp;
    printf("%u, (%u,%u)", tmp, a/tmp, b/tmp);
    return 0;
}

Answer 2

C#

This calculates the Bézout coefficients. I used the Extended Euclidean algorithm.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter your first number.");
            int firstNumber = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Enter your second number.");
            int secondNumber = Convert.ToInt32(Console.ReadLine());

            double max = Math.Max(firstNumber, secondNumber);
            double min = Math.Min(firstNumber, secondNumber);
            double s1 = 1;
            double s2 = 0;
            double t1 = 0;
            double t2 = 1;
            double quotient = 0;
            double remainder = 0;
            double[] remainders = new double[0];

            int i = 0;
            do
            {
                quotient = (int)(max / min);
                remainder = max - quotient * min;
                if (remainder > 0)
                {
                    Array.Resize(ref remainders, remainders.Length + 1);
                    remainders[i] = remainder;

                }
                if (i % 2 == 0)
                {
                    s1 = s1 - quotient * s2;
                    t1 = t1 - quotient * t2;
                }
                else
                {
                    s2 = s2 - quotient * s1;
                    t2 = t2 - quotient * t1;
                }

                if (i == 0)
                {
                    max = min;

                }
                else if (i >= 1)
                {
                    max = remainders[i - 1];
                }


                min = remainder;
                i++;
            } while (remainder > 0);

            Console.WriteLine((remainders[remainders.Length - 1]).ToString() + " " + (i % 2 == 0 ? "(" + s1 + "," + t1 + ")" : "(" + s2 + "," + t2 + ")"));
        }

    }
}

Answer 3

Javascript

Not cheap

Uses a lot of system resources.

function gcf(a, b) {
    var result = 1;
    for (var i = 1; i < 100000000 * a && i < 100000000/* Do it a few extra times, just to make sure */ * b; i++) {
        if (a % i == 0 && b % i == 0) {
            result = i;
        }
    }
    return [result, a / result, b / result];
}

Not fast

Use a callback, just as an extra failsafe.

function gcf(a, b) {
    setTimeout(function() {
        var result = 1;
        for (var i = 1; i < 2 * a && i < 2 * b; i++) {
            if (a % i == 0 && b % i == 0) {
                result = i;
            }
        }
        alert(result.toString() + " (" + (a / result).toString() + ", " + (b/result).toString() + ")");
    }, 10000);
}

Not good

Strict limit of gcf(10, 10), just to safe disk space.

function gcf(a, b) {
    var gcfTable = [[1,1,1,1,1,1,1,1,1,1],[1,2,1,2,1,2,1,2,1,2],[1,1,3,1,1,3,1,1,3,1],[1,2,1,4,1,2,1,4,1,2],[1,1,1,1,5,1,1,1,1,5],[1,2,3,2,1,6,1,2,3,2],[1,1,1,1,1,1,7,1,1,1],[1,2,1,4,1,2,1,8,1,2],[1,1,3,1,1,3,1,1,9,1],[1,2,1,2,5,2,1,2,1,10]];
    return [gcfTable[a - 1][b - 1], a / gcfTable[a - 1][b - 1], b / gcfTable[a - 1][b - 1]];
}

Answer 4

Perl 5

#!/usr/bin/perl
use strict;
use warnings;

$SIG{__WARN__} = sub { exit };

print(<<INTRO);
Greatest Common Factor

    goodbye           -- exit the application
    [number] [number] -- compute gcf of both numbers

INTRO

main();
sub main {
    print "> ";
    chomp(local $_ = <STDIN>);

    print "Have a good one.\n" and exit if /goodbye/;

    my @nums = /(-?\d+)/g;
    print "invalid input\n" and return main() if @nums != 2;

    my ($gcf, @coeff) = gcf(@nums);
    unless (grep abs($_) > 99, $gcf, @coeff) {
        select $\,$\,$\, rand for 1..10;
    }

    local $" = ", "; #"
    print "gcf(@nums) = $gcf\n";
    print "bezout coefficients: @coeff\n";
    main();
}

sub gcf {
    my ($x, $y) = @_;

    my @r = ($x, $y);
    my @s = (1, 0);
    my @t = (0, 1);

    my $i = 1;
    while ($r[$i] != 0) {
        my $q = int($r[$i-1] / $r[$i]);
        for (\@r, \@s, \@t) {
            $_->[$i+1] = $_->[$i-1] - $q * $_->[$i];
        }
        $i++;
    }

    return map int(1.01 * $_->[$i-1]), \@r, \@s, \@t;
}

__END__

Not cheap: main() is called recursively (filling up the stack) until a "deep recursion" warning is fired by perl which will quit the application due to the __WARN__ handler.

Not fast: When the gcf() algorithms returns correct results, the code just hangs on for a few seconds (select() in main()).

Not good: All results above 99 (or below -99) are incorrect.

All in all not so creative; looking forward to more elegant answers.

Answer 5

Python

#!/usr/bin/python
def gcd(x, y):
    l = 0
    if x < y:
        l = x
    else:
        l = y
    for g in reversed(range(l + 1)):
        if x%g == 0 and y%g == 0 and g > 1:
            return g
        else:
            if g == 1:
                return 1

def bezout(x,y,g):
    c1 = 0
    c2 = 0
    k = 0
    if x < y:
        k = y
    else:
        k = x
    for _k in range(k):
        tc = (gcd(x,y) - x*_k)%y
        if tc == 0:
            c1 = _k
            c2 = (gcd(x,y) - y*_k)/x
            return (c1, c2)

gc = gcd(15,9)
be, bf = bezout(9,15,gc)
print("%d (%d, %d)" % (gc, be, bf))

This is cheap and fast but it is bad in the fact that the range is capped at the largest input so it may not find a pair of coefficients.

Good puzzle.