4 days ago

my attempt to do the exercises in sicp.

## Thursday, June 26, 2008

### sicp exercise 1.17

; Exercise 1.17. The exponentiation algorithms in this section are based on performing exponentiation by

; means of repeated multiplication. In a similar way, one can perform integer multiplication by means of

; repeated addition. The following multiplication procedure (in which it is assumed that our language can

; only add, not multiply) is analogous to the expt procedure:

; (define (* a b)

; (if (= b 0)

; 0

; (+ a (* a (- b 1)))))

; This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition,

; operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using

; these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of

; steps.

(define (double a) (+ a a))

(define (halve a) (/ a 2))

(define (fast-mul-recur a b)

(cond ((= b 0) 0)

((even? b) (fast-mul-recur (double a) (halve b)))

(else (+ (fast-mul-recur (double a) (halve (- b 1))) a))))

(display (fast-mul-recur 10 9)) (newline)

(display (fast-mul-recur 99999 99999)) (newline)

(display (fast-mul-recur 9999999999999999999999999 9999999999999999999999999)) (newline)

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment