Add euclide ¯\_(ツ)_/¯

1 files changed, 36 insertions, 0 deletions

diff --git a/euclide.go b/euclide.go
new file mode 100644
index 0000000..77fd2d9
--- /dev/null
+++ b/euclide.go
@@ -0,0 +1,36 @@
+package main
+
+import "fmt"
+
+func main() {
+
+  N := 55
+  D := 13
+  
+  n := N
+  d := D
+
+  l := make([]int, 0)
+  
+  for d != 0 {
+    t := n/d
+    l = append(l, t)
+    r := n%d
+    n,d=d,r
+  }
+
+  fmt.Printf("PGCD(%d, %d) = %d\n", N, D, n)
+  fmt.Println(l, len(l))
+  gcd := n
+  
+  n,d = 1, l[len(l)-1]
+  for i := len(l) - 1 ; i >= 0 ; i-- {
+    t := n+d*l[i]
+    n,d = d,t
+  }
+  if len(l) & 1 == 1 {
+    n,d=-n,-d
+  }
+
+  fmt.Printf("%d*%d - %d*%d = %d = %d\n", N, n, D, d, gcd, n*N-d*D)
+}