git.iko.soy/urbit.org
on 492ae2f help sign in
urbit.org/docs/programming/reference/library/src/3a/gate/egcd.md
42 lines 968 B history raw
1### `++egcd`
3GCD
5 ++ egcd !: :: schneier's egcd
6 |= {a/@ b/@}
7 =+ si
8 =+ [c=(sun a) d=(sun b)]
9 =+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
10 |- ^- {d/@ u/@s v/@s}
11 ?: =(--0 c)
12 [(abs d) d.u d.v]
13 :: ?> ?& =(c (sum (pro (sun a) c.u) (pro (sun b) c.v)))
14 :: =(d (sum (pro (sun a) d.u) (pro (sun b) d.v)))
15 :: ==
16 =+ q=(fra d c)
17 %= $
18 c (dif d (pro q c))
19 d c
20 u [(dif d.u (pro q c.u)) c.u]
21 v [(dif d.v (pro q c.v)) c.v]
22 ==
23 ::
26Greatest common denominator
28 ~zod/try=> (egcd 20 15)
29 [d=5 u=2 v=1]
30 ~zod/try=> (egcd 24 16)
31 [d=8 u=2 v=1]
32 ~zod/try=> (egcd 7 5)
33 [d=1 u=3 v=6]
34 ~zod/try=> (egcd (shaf ~ %ham) (shaf ~ %sam))
35 [ d=1
36 u=59.983.396.314.566.203.239.184.568.129.921.874.787
37 v=38.716.650.351.034.402.960.165.718.823.532.275.722
38 ]
42***