Euclidean Algorithm

Let’s create a Euclidean algorithm for searching x and y for some integers a and b that

ax + by = gcd(a,b),

where gcd() is the greatest common divisor of a and b.

Searching for gcd(a,b)

We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:

gcd(a, b) = gcd(b, a%b)

The algorithm of gcd(a, b) stops when b=0, and the answer is a.

Euclidean Algorithm Realization

Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)y1 = ay1 + b(x1-a//by1).

Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:

x = y1

y = x1-a//b*y1.

We'll use this fact in the algorithm.

Tehtävä

Swipe to start coding

Complete the Euclidean Algorithm and test it.

Ratkaisu

#returns g = gcd(a,b), x and y in one tuple

def gcd(a, b):

# special case: a must be greater than b. We call function for swapped a and b

if a < b:

a, b = b, a

#place where algorithm stops

if b==0:

return a, 1, 0

g, x1, y1 = gcd(b, a%b)

# replace x and y with values, using x1 and y1

x = y1

y = x1-a//b*y1

return g, x, y

print(gcd(140, 312))

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 4

#returns g = gcd(a,b), x and y in one tuple

def gcd(a, b):

# special case: a must be greater than b. We call function for swapped a and b

if a < b:

a, b = b, a

#place where algorithm stops

if ____:

return a, 1, 0

g, x1, y1 = gcd(b, a%b)

# replace x and y with values, using x1 and y1

x = _

y = __________

return g, x, y

#call function for a=140 and b=312

print(gcd(_______))

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme