Skip to content

Instantly share code, notes, and snippets.

@raphiz
Created January 24, 2016 14:10
Show Gist options
  • Save raphiz/668e849905d6113f2a3e to your computer and use it in GitHub Desktop.
Save raphiz/668e849905d6113f2a3e to your computer and use it in GitHub Desktop.
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
else:
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
else:
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