3
\$\begingroup\$

From SICP's 1.24: (Exponentiation)

(you may need to click through and read ~1 page to understand)

Exercise 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. (Hint: Using the observation that (bn/2)2 = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

I wrote the following solution:

(define (even n) (= (remainder n 2) 0))

(define (fast-expt b n)
  (fast-expt-iter b b n))

(define (fast-expt-iter a b n)
  (cond ((= n 1) a)
    ((even n) (fast-expt-iter (* a b) b (/ n 2)))
    (else (fast-expt-iter (* a b) b (- n 1)))))

Do you think my solution is correct? Moreover, what do you think about my code?

\$\endgroup\$
  • 1
    \$\begingroup\$ even? is a Scheme builtin, so you should not define your own version. :-) Also, your bottom version isn't iterative. \$\endgroup\$ – Chris Jester-Young Jun 19 '12 at 2:59
4
\$\begingroup\$

Your implementation will not produce correct results in general because your recursive definitions are erroneous.

One should note that in case n = 0, result is 1. In case of even n (or n = 2 i), one may write b ^ n = (b * b) ^ i. In case of odd n (or n = 2 i + 1), one may write b ^ n = b * (b * b) ^ i. Here's an implementation (using if's instead of cond and folding the two recursive steps into one):

(define (fast-expt b n)
  (if (= n 0) 1
      (* (if (= (remainder n 2) 0) 1 b) (fast-expt (* b b) (quotient n 2)))))

To make this definition iterative, use the accumulator, a, that is initially 1. When n is even (n = 2 i), square b but keep a unchanged. This maintains the property b ^ n = a * (b ^ 2) ^ i. When n is odd (n = 2 i + 1), square b and multiply a by b. This maintains the property b ^ n = (a * b) * (b ^ 2) ^ i. Thus, we have:

(define (fast-expt b n)
  (fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
  (if (= n 0) a
      (fast-expt-iter (* a (if (= (remainder n 2) 0) 1 b)) (* b b) (quotient n 2))))
\$\endgroup\$
  • \$\begingroup\$ This doesn't work for (fast-expt 2 2) - it returns 2, which should be 4, shouldn't it? \$\endgroup\$ – jaresty Mar 28 '11 at 3:59
  • \$\begingroup\$ @jaresty: You're absolutely right. I screwed up my recursive definition. =) I'm editing my answer. \$\endgroup\$ – Adeel Zafar Soomro Mar 28 '11 at 5:35
  • \$\begingroup\$ Hmm... I'm a bit confused. The problem asked for an "iterative solution," but I feel like the solution we arrived at is somehow more recursive than iterative. What do you think? \$\endgroup\$ – jaresty Mar 28 '11 at 7:03
  • \$\begingroup\$ @jaresty: Agreed. I forgot to include the iterative version. Edited it into the answer. \$\endgroup\$ – Adeel Zafar Soomro Mar 28 '11 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.