Initial commit master
authoraskhader <yayo23@gmail.com>
Mon, 27 Jun 2011 15:56:06 +0000 (11:56 -0400)
committeraskhader <yayo23@gmail.com>
Mon, 27 Jun 2011 15:56:06 +0000 (11:56 -0400)
go/diophant.go [new file with mode: 0644]
scheme/euclidean.ss [new file with mode: 0644]

diff --git a/go/diophant.go b/go/diophant.go
new file mode 100644 (file)
index 0000000..d71d145
--- /dev/null
@@ -0,0 +1,18 @@
+/* package diophant implements linear diophantine equations */
+package diophant
+
+type Equation struct {
+    a int
+    b int
+    c int
+}
+
+Type Solution sturct {
+    x int
+    y int
+}
+
+func NewEquation(a, b. c int) *Equation {
+    e := Equation(a, b, c)
+    return &e;
+}
diff --git a/scheme/euclidean.ss b/scheme/euclidean.ss
new file mode 100644 (file)
index 0000000..8c02e6d
--- /dev/null
@@ -0,0 +1,64 @@
+#lang scheme
+
+(provide divides? solvable? make-diophant eea
+         eea-solution? printdio e e_solved)
+
+; equations are comprised of
+; '((5 x) (3 y) 18)
+(define-struct monomial (constant identifier))
+(define-struct diophant (a b c))
+(define-struct solution (x y))
+
+; structure printing
+(define (printdio eqn)
+  (let ((a (diophant-a eqn))
+        (b (diophant-b eqn))
+        (c (diophant-c eqn)))
+    (printf "~ax + ~ay = ~a~n" a b c)))
+
+; predicate for divisibility
+(define (divides? a b) (= (remainder b a) 0))
+
+;determines if a linear diophantine equation has a solution
+(define (solvable? eqn)
+    (divides? (gcd (diophant-a eqn) (diophant-b eqn))
+              (diophant-c eqn)))
+
+; extended euclidean algorithm
+; return a single solution '(x y)
+; diophant -> solution
+(define (eea eqn)
+  (let ((a (diophant-a eqn))
+        (b (diophant-b eqn))
+        (c (diophant-c eqn)))
+     ; euclidean algo
+     (define (ea s q0 x y x0 y0)
+       (let* ((q (quotient s q0))
+              (r (remainder s q0)))
+         (printf "~a = (~a)(~a) + ~a ~n"
+                s q0 q r)
+         (cond [(= r 0) (list x y)]
+               [true (ea q0 
+                          r 
+                          (+ (* (- q) x) x0)
+                          (+ (* (- q) y) y0)
+                          x 
+                          y)])))
+    (cond [(> b a) (reverse (eea (make-diophant b a c)))]
+          [(divides? a c) (list (quotient c a) 0)]
+          [(divides? b c) (list 0 (quotient c b))]
+          [true (let* ((z (quotient c (gcd a b))))
+                  (map (lambda (x) (* z x))
+                       (ea a b 0 1 1 0))) ])))
+
+; determine if a solution to the equation is correct
+; diophant, solution -> bool
+(define (eea-solution? eqn soln)
+  (let ((a (diophant-a eqn))
+        (b (diophant-b eqn))
+        (c (diophant-c eqn)))
+    (= (+ (* a (car soln)) (* b (cadr soln))) c)))
+
+; test definitions
+(define e (make-diophant 7 19 151))
+(define e_solved (eea e))