Explanation for the Euclid Extended Algorithm

Question

Please this is how the code for the extended-euclid algorithm was implemented in the book Introduction to Algorithm (Chapter 31 page 937

EXTENDED-EUCLID(a,b)

if b == 0

return (a,1,0)

else (d_1,x_1,y_1) = EXTENDED-EUCLID(b,a mod b)

$(d,x,y) = (d_1,y_1,x_1 - \lfloor \frac{a}{b} \rfloor)$

return(d,x,y)

Then I tried to implement it in python

def extended_euclid(a,b):
    if b == 0:
        return (a,1,0)
    else:
        (d_1,x_1,y_1) = extended_euclid(b, a % b)
        (d,x,y) = (d_1,y_1,x_1 - (a//b) * y_1)
        return (d,x,y)

But when I run the function with input (99,78) it returns (3, -11, 14)

But the explanation the book gave about how to to find the EXTENDED-EUCLID(99,78) using the above algorithm was

Step 1: The algorithm returns (3,-11,14)

Step 2: The algorithm returns (3,3,-11)

Step 3: The algorithm returns (3,-2,3)

Step 4: The algorithm returns (3,1,-2)

Step 5: The algorithm returns (3,0,1)

Step 6: The algorithm returns (3,1,1)

So I was expecting the final output from the code I wrote to be (3,1,1). Please can someone explain why I am not getting similar answer ?

Answer 1

The steps are given in reverse order. The $(3,1,1)$ should be $(3,1,0)$. You can see what is going on by using print() function before returning.

def extended_euclid(a,b):
    if b == 0:
        print([a,b],[a,1,0]);
        return (a,1,0)
    else:
        (d_1,x_1,y_1) = extended_euclid(b, a % b)
        (d,x,y) = (d_1,y_1,x_1 - (a//b) * y_1)
        print([a,b],[d,x,y]);
        return (d,x,y)

If you execute extended_euclid(99,78) then the resulting output is

[3, 0] [3, 1, 0]
[6, 3] [3, 0, 1]
[15, 6] [3, 1, -2]
[21, 15] [3, -2, 3]
[78, 21] [3, 3, -11]
[99, 78] [3, -11, 14]

while the function returns [3,-11,14]. This means that $$ 3 = (-11)\cdot 99 + (14)\cdot 78 = -1089 + 1092 $$ is the gcd $\,3\,$ expressed as a linear combination of the two numbers $\,99,78.$