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.
Oplossing
Bedankt voor je feedback!
single
Vraag AI
Vraag AI
Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.
Vat dit hoofdstuk samen
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 7.69
Euclidean Algorithm
Veeg om het menu te tonen
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.
Oplossing
Bedankt voor je feedback!
Awesome!
Completion rate improved to 7.69single