ex1.17.rkt

#lang scheme
;; Exercise 1.17
;; The exponentiation algorithm 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 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 (fast-mult a b)
  (cond
    ((= b 0) 0)
    ((= b 1) a)    
    ((even? b) (fast-mult (double a) (halve b)))
    (else (+ a (fast-mult a (- b 1))))))

; Sample Run
; (* 2 4)
; (+ 4 (* 2 2))
; (+ 4 (+ 4 (* 2 1)))
; (+ 4 (+ 4 2))
; (+ 4 6)
; 8

(define (double x) (* x 2))
(define (halve x)
  (cond
    ((even? x) (/ x 2))))