# weima learns to program

my attempt to do the exercises in sicp.

## Saturday, March 13, 2010

### sicp exercise 3.30

;; Exercise 3.30.  Figure 3.27 shows a ripple-carry adder formed by stringing together n full-adders. This is the simplest form of parallel adder for adding two n-bit binary numbers. The inputs A1, A2, A3, ..., An and B1, B2, B3, ..., Bn are the two binary numbers to be added (each Ak and Bk is a 0 or a 1). The circuit generates S1, S2, S3, ..., Sn, the n bits of the sum, and C, the carry from the addition. Write a procedure ripple-carry-adder that generates this circuit. The procedure should take as arguments three lists of n wires each -- the Ak, the Bk, and the Sk -- and also another wire C. The major drawback of the ripple-carry adder is the need to wait for the carry signals to propagate. What is the delay needed to obtain the complete output from an n-bit ripple-carry adder, expressed in terms of the delays for and-gates, or-gates, and inverters?

(define (ripple-carry-adder A B S N C)
(define (iter a AA b BB s SS c-in n)
(let ((c-out (make-wire)))
(if (not (= n N))
(begin (full-adder a b c-in s c-out)
(iter (car AA) (cdr AA)
(car BB) (cdr BB)
(car SS) (cdr SS)
c-out (+ 1 n))))))
(iter (car A) (cdr A)
(car B) (cdr B)
(car S) (cdr S)
C 1))