Exercises 1.16, 1.17, 1.18

1.16 Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.

From the hints

• (b^n/2)² = (b²)^n/2
• abⁿ should have the same value through the transition.

I want to decrease the exponent until it equals zero, at which point the result variable, a, will have the result. So the question is, when I halve the exponent n, how can I modify a and b so that abⁿ is unchanged, and that we're somehow closer to the result?

So my strategy is:

• If n is even, halve n, square b, and leave a alone
• If n is odd, decrement n by 1, and multiply a by b.

Here is the procedure.

(define (fast-iter-expt x y)
  (define (fast-helper a b n)
    (cond ((= 0 n) a)
          ((odd? n) (fast-helper (* b a) b (- n 1)))
          ((even? n) (fast-helper a (* b b) (/ n 2)))))
  (fast-helper 1 x y))

1.17 Design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

Referring back to the text for the exponent procedure, I come up with a method for determining multiplication, analogous to the exponentiation method in the text.

• ab = 2(a x ^b⁄₂), if b is even
• ab = a + a(b-1) if b is odd

This translates to the procedure.

(define (double n)
  (+ n n))

(define (halve n)
  (if (even? n)
      (/ n 2)
      (error "Tried to halve an odd number" n)))

(define (mult-r a b)
  (cond ((= b 0) 0)
        ((odd? b) (+ a (mult-r a (- b 1))))
        ((even? b) (double (mult-r a (halve b))))))

1.18 An iterative version of 1.17.

I came up with an invariant quantity, as described in the hint for 1.14

• ab+r = 2a⋅^b⁄₂ + r, when b is even
• ab+r = a(b-1) + (result + a), when b is odd

This translates to the procedure:

(define (mult-i a b)
  (define (multi-helper a b result)
    (cond ((= b 0) result)
          ((odd? b) (multi-helper a (- b 1) (+ result a)))
          ((even? b) (multi-helper (double a) (halve b) result))))
  (multi-helper a b 0))