1
\$\begingroup\$

Given the following task:

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.

I wrote this solution:

(define (double a) (* a 2))
(define (halve a) (/ a 2))
(define (even n) (= (remainder n 2) 0))

(define (times a b)
  (cond ((= 1 b) a)
        ((even b) (times (double a) (halve b)))
        (else (times (+ a a) (- b 1)))))

What do you think?

\$\endgroup\$
2
\$\begingroup\$

Your implementation will not produce correct results in general.

In the base case of b = 0, result should be 0. In the case of even b, result is double a times half b (which you have done correctly). In the case of odd b, result should be a + (double a times half (b - 1)).

(define (times a b)
  (cond ((= 0 b) 0)
        ((even b) (times (double a) (halve b)))
        (else (+ a (times (double a) (halve (- b 1)))))))

To make this definition iterative, add an accumulator, like so:

(define (times a b)
  (times-iter 0 a b))

(define (times-iter acc a b)
  (cond ((= 0 b) acc)
        ((even b) (times-iter acc (double a) (halve b)))
        (else (times-iter (+ a acc) (double a) (halve (- b 1))))))
\$\endgroup\$
  • \$\begingroup\$ How would you write this as an iterative solution, as per exercise 1.18 on mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html ? \$\endgroup\$ – jaresty Mar 28 '11 at 7:24
  • \$\begingroup\$ @jaresty: Edited my answer to include an iterative solution. \$\endgroup\$ – Adeel Zafar Soomro Mar 28 '11 at 7:39
  • \$\begingroup\$ Can you explain the difference between recursive and iterative? \$\endgroup\$ – jaresty Mar 28 '11 at 9:48
  • \$\begingroup\$ @jaresty: Recursion is the process of solving a problem by restating it in terms of a smaller example of the same problem. This is usually done by calling a procedure from within itself, with arguments that tend toward the base cases, and passing back the results of the call in order to build a solution. Iteration is the process of rerunning a collection of statements with changing variables until a terminating condition is met. Iteration may be implemented in a number of ways: as a loop or, in the case of Scheme, as a tail-call optimized recursion. \$\endgroup\$ – Adeel Zafar Soomro Mar 28 '11 at 18:53

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.