Aug-27-2020, 06:57 PM
Hi,
I have an assignment where I was given a pseudo code based off of Stein's algorithm to get GCD. The pseudo code provided was:
k := 0
while x and y are both even
x := x / 2
y := y / 2
k := k + 1
while x ≠ y
if x is even then x := x/2
else if y is even then y := y/2
else if x > y then x := (x – y)/2
else y := (y – x)/2
return x × 2k
I tried coding a function based off the pseudo code I was given but when I run the function, it does not solve at all. No answer is given and the code just keeps running. Can I have some help with this?
Code I wrote:
I have an assignment where I was given a pseudo code based off of Stein's algorithm to get GCD. The pseudo code provided was:
k := 0
while x and y are both even
x := x / 2
y := y / 2
k := k + 1
while x ≠ y
if x is even then x := x/2
else if y is even then y := y/2
else if x > y then x := (x – y)/2
else y := (y – x)/2
return x × 2k
I tried coding a function based off the pseudo code I was given but when I run the function, it does not solve at all. No answer is given and the code just keeps running. Can I have some help with this?
Code I wrote:
def gcd(x, y): k=0 while x%2==0 and y%2==0: x=x/2 y=y/2 k=k+1 while x%2!=0 or y%2!=0: while x%2==0: x=x/2 while y%2==0: y=y/2 while x>y: x=(x-y)/2 while y>x: y=(y-x)/2 return x*(2**k)Thanks for any help!