An example for illustrating the algorithm: 3 * 10 = 3 * (2 * (10 / 2)) = 3 * (2 * 5) = 6 * 5 = 6 * (4 + 1) = 6 * 4 + 6 = 6 * (2 * (4 / 2)) + 6 = 6 * (2 * 2) + 6 = 6 * 2 * 2 + 6 = 12 * 2 + 6 = 24 + 6 = 30.

  
 ;; ex 1.17 
  
 ;; Assume double and halve are defined by the language 
 (define (double x) (+ x x)) 
 (define (halve x) (/ x 2)) 
  
 (define (* a b) 
   (cond ((= b 0) 0) 
         ((even? b) (double (* a (halve b)))) 
         (else (+ a (* a (- b 1)))))) 
  
 ;; Testing 
 (* 2 4) 
 (* 4 0) 
 (* 5 1) 
 (* 7 10)

Here is an illustration of the recursive process:

 ; (fast-mult 3 7) 
 ; (+ 3 (fast-mult 3 6)) 
 ; (+ 3 (double (fast-mult 3 3)) 
 ; (+ 3 (double (+ 3 (fast-mult 3 2)))) 
 ; (+ 3 (double (+ 3 (double (fast-mult 3 1))))) 
 ; (+ 3 (double (+ 3 (double (+ 3 (fast-mult 3 0)))))) 
 ; (+ 3 (double (+ 3 (double (+ 3 0))))) 
 ; (+ 3 (double (+ 3 (double 3)))) 
 ; (+ 3 (double (+ 3 6))) 
 ; (+ 3 (double 9)) 
 ; (+ 3 18) 
 ; 21

using tail recursion achieves better space order of growth of theta(1)

  
 (define (fast-mult-by-add a b) 
   (define (double x) (+ x x)) 
   (define (halve x) (/ x 2)) 
    
   (define (helper a b product) ;; "add a" b times 
     (cond ((= b 0) product) 
           ((even? b) (helper (double a) (halve b) product)) 
           (else (helper a (- b 1) (+ a product))))) 
   (helper a b 0))

bob

Isn't this version just skipping ahead to the next one, Exercise 1.18?

ybsh

I agree with Bob. The problem instruction requires readers to implement a procedure analogous to fast-expt (from 1.2.4), which evolves into a recursive process, not an iterative one. Anyway, nice explanation.

master

Doesn't this accomplish the same thing but more efficiently? No need to delay the doubling.

 (define (double x) (+ x x)) 
 (define (halve x) (/ x 2)) 
  
 (define (fast-mult a b) 
   (cond ((= b 0) 0) 
         ((even? b) (fast-mult (double a) (halve b))) 
         (else (+ a (fast-mult a (- b 1))))))

bidouille

I also made the master way. Not sure it changes about efficiency, but at least I find it more readable :)

jazbot

I came up with the following solution, which seems to execute fewer calls than the solutions listed above:

 (define (fast-* a b) 
   (cond ((= b 1) 
          a) 
         ((even? b) 
          (double (fast-* a (halve b)))) 
         (else 
           (+ a (double (fast-* a (halve (- b 1))))))))

For example if I calculate the product of 3 and 10,000,000, my solution uses 24 calls, while both of the solutions above use 32.

anon

I like the modification by jazbot to call the procedure once instead of twice for odd b but i believe the procedure would throw an error for b=0. For most use cases, the condition of b=1 catches the reduction of b through the recursive process but if you start with b=0, then you should run into an issue.

Easily solved by adding in another condition though.

sicp-ex-1.17