"Extended Euclidean algorithm"의 두 판 사이의 차이
ph
(새 문서: [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm wiki] python code is as follows, <pre> def exteuclid(m, n, s0=1, s1=0, t0=0, t1=1): # s0 := s_{i-1} # s1 := s_i...) |
잔글 |
||
| 14번째 줄: | 14번째 줄: | ||
t = t0 - q*t1 | t = t0 - q*t1 | ||
if r==0: | if r==0: | ||
| − | return | + | return n, s1, t1 |
else: | else: | ||
return exteuclid(n, r, s1, s, t1, t) | return exteuclid(n, r, s1, s, t1, t) | ||
2017년 8월 11일 (금) 15:39 판
python code is as follows,
def exteuclid(m, n, s0=1, s1=0, t0=0, t1=1):
# s0 := s_{i-1}
# s1 := s_i
# t0 := t_{i-1}
# t1 := t_i
assert m>=n
q = m/n
r = m%n
s = s0 - q*s1
t = t0 - q*t1
if r==0:
return n, s1, t1
else:
return exteuclid(n, r, s1, s, t1, t)
#test
#print exteuclid(240, 46)
#(2, -9, 47)