summaryrefslogtreecommitdiffstats
path: root/šola/la/dn4/gcd.r
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--šola/la/dn4/gcd.r29
1 files changed, 29 insertions, 0 deletions
diff --git a/šola/la/dn4/gcd.r b/šola/la/dn4/gcd.r
new file mode 100644
index 0000000..5d10a40
--- /dev/null
+++ b/šola/la/dn4/gcd.r
@@ -0,0 +1,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))
+}