sicp-ex-3.30



<< Previous exercise (3.29) | Index | Next exercise (3.31) >>


3pmtea

  
 ;; 
 (define (ripple-carry-adder a-list b-list s-list c) 
   (let ((c-list (map (lambda (x) (make-wire)) (cdr a-list))) 
         (c-0 (make-wire))) 
     (map full-adder 
          a-list 
          b-list 
          (append c-list (list c-0)) 
          s-list 
          (cons c c-list)) 
     'ok)) 
  
  
 ;;a 
 (define (ripple-carry-adder Ak Bk Sk C) 
   (define (iter A B S c-in c-out) 
     (if (null? A) 
         S 
         (begin (full-adder (car A) (car B) 
                            c-in (car S) c-out) 
                (iter (cdr A) (cdr B) (cdr S) 
                      (c-out) (make-wire))))) 
   (iter Ak Bk Sk C (make-wire))) 
  
  
  
 ;;a 
 (define (ripple-carry-adder a b s c) 
   (let ((c-in (make-wire))) 
         (if (null? (cdr a)) 
           (set-signal! c-in 0) 
           (ripple-carry-adder (cdr a) (cdr b) (cdr s) c-in)) 
         (full-adder (car a) (car b) c-in (car s) c))) 
  
  
 (define (ripple-carry-adder a b c-in sum) 
     (if (not (null? a)) 
         (let ((carry (make-wire))) 
               (full-adder         (car a) (car b) c-in (car sum) carry) 
               (ripple-carry-adder (cdr a) (cdr b) carry (cdr sum))))) 
  
  
 ;;some convinience methods to test the adder 
 (define (build-wires input-signals) 
         (if (null? input-signals) 
             '() 
             (let ((new-wire (make-wire))) 
                  (set-signal! new-wire (car input-signals)) 
                  (cons new-wire (build-wires (cdr input-signals)))))) 
                 
 (define (get-signals wires) 
       (map (lambda (w) (get-signal w)) wires)) 
  
  
 ;;biggest digit first 
 (define (to-binary number) 
         (if  (< number 2) 
              (list number) 
              (cons (mod number 2) (to-binary (div number 2)) ))) 
  
 ;;simulation 
 (define the-agenda (make-agenda)) 
 (define inverter-delay 1) 
 (define and-gate-delay 1) 
 (define or-gate-delay 1) 
  
 (define a (build-wires '(0 0 1 0 0 0))) ;;4 
 (define b (build-wires '(1 1 0 1 0 0))) ;;11 
 (define s (build-wires '(0 0 0 0 0 0))) 
 (define c-in (make-wire)) 
 (ripple-carry-adder a b c-in s) 
  
 (propagate) 
 (get-signals s) ;;should be 15 

Added a couple of convenience procedures if someone wants to play with adders and multipliers

the delays of An or Bn are always 0,so the delays of Cn and Sn are only depends on Cn-1-delay. the recursion formula of Cn-delay is

(+ Cn-1-delay
   (* 2 and-gate-delay)
   or-gate-delay
   (max or-gate-delay
        (+ and-gate-delay
           inverter-delay)))

and C0-delay equals 0,so the general formula of Cn-delay is

(+ (* 2 n and-gate-delay)
   (* n or-gate-delay)
   (* n (max or-gate-delay
             (+ and-gate-delay
                inverter-delay)))

Sn-delay is

(+ Cn-1-delay
   (* 2
      and-gate-delay)
   (* 2
      (max or-gate-delay
           (+ and-gate-delay
              inverter-delay))))

equals

(+ (* 2 n and-gate-delay)
   (* (- n 1) or-gate-delay)
   (* (+ n 1) (max or-gate-delay
                   (+ and-gate-delay
                      inverter-delay)))