;;; A Goedelian representation of ratls
;;; That is, the number n/d is represented by
;;;       2^{|n|} * 3^{|d|} * 5 if n/d is positive,
;;; or by 2^{|n|} * 3^{|d|} if n/d is negative.
;;; The ability to extract the numerator and denominator
;;; comes from the unique factorization of numbers into primes.
;;;
;;; AUTHOR: Gary T. Leavens

(define make-ratl
  (lambda (int1 int2)
    (if (zero? int2)
        (error "make-ratl: The denominator cannot be zero.")
        (* (expt 2 (abs int1))
	   (expt 3 (abs int2))
	   (expt 5 
		 (sign-code (* int1 int2)))))))

(define numr
  (lambda (rtl)
    (* (sign-decode rtl)
       (factors rtl 2))))

(define denr
  (lambda (rtl)
    (factors rtl 3)))

(define sign-code ; TYPE: (-> (number) integer)
  (lambda (n)
    ; ENSURES: give the code in this representation for the sign of n
    (if (positive? n) 1 0)))

(define sign-decode ; TYPE: (-> (rational) integer)
  (lambda (rtl)
    ; ENSURES: result is -1 if rtl is negative, +1 otherwise
    (if (zero? (factors rtl 5))
	-1
	1)))
	
(define factors ; TYPE: (-> (natural natural) natural)
  (lambda (n divisor)
    ; REQUIRES: divisor is not 0
    ; ENSURES: divisor raised to the result power = n
    (if (evenly-divides? n divisor)
	(add1 (factors (/ n divisor)
		      divisor))
	0)))

(define evenly-divides? ;TYPE: (-> (natural natural) boolean)
  (lambda (n d)
    ; REQUIRES: divisor is not 0
    ; ENSURES: result is #t iff d evenly divides n
    (zero? (remainder n d))))