Inspired by Cheap, Fast, Good, we're going to implement an algorithm which has exactly two of them.
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
d = 3 x = 2 y = -3
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.
Your program should take two integers as inputs. It should output/return the greatest common factor and one pair of Bézout coefficients.
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.
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!
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.