(load "tester.scm")

; GCD (greatest common divisor) using a hardware model

; functional definition

; gcd of two non-negative integers
; one of them must be non-zero (otherwise gcd is undefined)

(define (gcd m n)
  (if (= m n)
      m
      (if (< m n)
          (gcd (- n m) m)
          (gcd n m))))

(test (gcd 24 36) 12)
(test (gcd 42 18) 6)
(test (gcd (* 3 7 11 17 37) (* 5 7 13 17 41)) (* 7 17)) 


; hardware model

; The ALU is a combinational unit that provides three things:
;    first:  An indication of whether the two values are =
;    second: An indication of whether m is less than n
;    third:  The difference (- n m)

(define (ALU m n)
  (list
   (= m n)
   (< m n)
   (- n m)))

; The hardware-gcdfunction provides the control aspect.
; It looks at the (= m n) value of the ALU output. If true, it stops.
; Otherwise, it continues with new values in the m and n register.
; The n register always gets m. The m register gets either (-n m) 
; or n depending on the (< m n) value.

(define (hardware-gcd m n)
  (let (
        (alu-output (ALU m n))
        )
    (if (first alu-output)
        m
        (hardware-gcd
         (multiplexer (second alu-output) (third alu-output) n)
         m))))

; The multiplexer selects one of two inputs, depending on the first argument.

(define (multiplexer choice a b)
  (if choice a b))

(test (hardware-gcd 24 36) 12)
(test (hardware-gcd 42 18) 6)
(test (hardware-gcd (* 3 7 11 17 37) (* 5 7 13 17 41)) (* 7 17)) 

(tester 'show)