Skip to content

Instantly share code, notes, and snippets.

@raphiz raphiz/
Created Jan 24, 2016

What would you like to do?
A quick & dirty implementation of the Euclidean algorithm in python
#!/usr/bin/env python
# coding=utf-8
from tabulate import tabulate
a = 180
b = 101
def euklid(x_p, y_p, q_p=None, r_p=None, u_p=None, s_p=None, v_p=None, t_p=None, result=None):
if result is None:
result = []
x, y = x_p, y_p
u, s, v, t = 1, 0, 0, 1
x = y_p
y = r_p
u, v = s_p, t_p
s = u_p - (q_p*s_p)
t = v_p - (q_p*t_p)
q = int(x/y)
r = x % y
result.append([x, y, q, r, u, s, v, t])
if r == 0:
return result
return euklid(x, y, q, r, u, s, v, t, result)
result = euklid(a, b)
print(tabulate(result, ['x', 'y', 'q', 'r', 'u', 's', 'v', 't'], tablefmt="fancy_grid"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.