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.
Swipe to start coding
Complete the Euclidean Algorithm and test it.
Løsning
Takk for tilbakemeldingene dine!
single
Spør AI
Spør AI
Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår
Oppsummer dette kapittelet
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 7.69
Euclidean Algorithm
Sveip for å vise menyen
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.
Swipe to start coding
Complete the Euclidean Algorithm and test it.
Løsning
Takk for tilbakemeldingene dine!
Awesome!
Completion rate improved to 7.69single