šola/la/dn4/gcd.r


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

polygcd <- function (a, b) {
	rp <- a
	sp <- 1
	tp <- 0
	r <- b
	s <- 0
	t <- 1
	while (any(r != 0)) {
		print(list("debug"=list("r"=r, "s"=s, "t"=t)))
		rs <- r
		ss <- s
		ts <- t
		korak <- function (t, p) {
			odstrani_ničle <- function (v) {
				if (all(v == 0))
					return(v)
				return(v[min(which(v!=0)):max(which(v!=0))])
			}
			return(p-polymul(odstrani_ničle(t), polydiv(odstrani_ničle(r), odstrani_ničle(rp))$d))
		}
		r <- korak(r, rp)
		s <- korak(s, sp)
		t <- korak(t, tp)
		rp <- rs
		sp <- ss
		tp <- ts
	}
	return(list("r"=rp, "s"=sp, "t"=tp))
}