- #1
Tony11235
- 255
- 0
{x = A, y = B}
begin
while x != y do
if x < y
then y := y - x
else x := x - y
end
{x = gcd(A, B)}
How do I prove that the program above is correct? A and B are whole numbers and gcd(A, B) stands for Greatest Commom Divisor. What's the best method for proving that it computes the gcd of A and B? It's not written in any specific language.
begin
while x != y do
if x < y
then y := y - x
else x := x - y
end
{x = gcd(A, B)}
How do I prove that the program above is correct? A and B are whole numbers and gcd(A, B) stands for Greatest Commom Divisor. What's the best method for proving that it computes the gcd of A and B? It's not written in any specific language.