CODEWITHSUNDEEP
pythondiscrete-mathematics
KeKJA
KeKJA

Reputation: 1

Euclidean Algorithm for solving an equation but there is a bug

def kek(k,p):
    if k > p:
        return pew(k,p)
    elif k < p:
        return pew(p,k)
    else:
        return 1
def pew(j,k):
    if k == 0:
        return j,j,k
    q = j // k
    r = j % k
    R, h , o = pew(k,r)
    return R,o,h-q*o    
hmm = kek(231,1920)

'''
Math logic:
d = s x 231 + t x 1920
1920 = 8*231 + 72
231 = 3*72 + 15
72 = 4*15 + 12
15 = 1*12 + 3
12 = 4*3
d = gcd(231, 1920) = 3
3 = 15 – 12 
= 15 – (72 – 4*15) 
= 15 – 72 + 4*15 
= 5*15 – 72 
= 5*(231-3*72) – 72
= 5*231 – 15*72 – 72 
= 5*231 – 16*72 
= 5*231 – 16*(1920-8*231)
= 5*231 – 16*1920 + 128*231
= 133*231 – 16*1920 
= 133*231 + (-16)*1920
d = 3, s = 133 , t = -16
'''

However, I got -48 for s and 399 for t and a correct result 3 for d. Where is the problem with my recursive method? The above Math logic is how you calculate it by hand, I used D = bR1 + (a-Qb)R2 and D = aR2 + b*R3 to achieve my resursive call, but it gives me the results of 133 * 3 and -16 * 3 which is what I don't want to get.

Upvotes: 0

Views: 70

Answers (1)

dangee1705
dangee1705

Reputation: 3520

Your code is quite hard to follow but I came up with a different solution which does the same thing.

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x

print(egcd(231, 1920)) # (3, 133, -16)

Upvotes: 2

Related Questions