# Cheap, Fast, Good - Common Factor (Greatest) [closed]

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.

• It's nice to have an original challenge like this. :) May 11 '14 at 13:31
• Does the program have to be exactly two at once or is it OK if it's only good in some cases and cheap and fast (but not good) in others? Jun 9 '14 at 21:37
• I'm looking for three cases, with exactly two in each. Jun 9 '14 at 22:57
• If the program is not good it's output should be incorrect? Then what is the point of calculating anything correctly? Jun 11 '14 at 23:47
• I'm voting to close this question as off-topic because it's an [underhanded] challenge, which was on-topic a year ago, but is now off-topic by community consensus. Apr 23 '16 at 20:23

# 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;
}


## 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;

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 + ")"));
}

}
}

• When is this expensive, when is it slow, and when is it bad? May 12 '14 at 15:16
• @undergroundmonorail I will put those values when I have the chance. May 12 '14 at 15:22

# 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.

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.

# 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]];
}

• When is it cheap and fast but not good? Jun 9 '14 at 3:34
• This answer is cheap, good, but not fast. Aug 3 '14 at 18:53
• the challenge is to write a program that is each of "not cheap", " not fast ", and " not good " in different circumstances. Aug 3 '14 at 19:21
• Answer fixed... Aug 3 '14 at 19:45