excercise1.14~1.19.rkt

#lang racket

;; Excercise 1.14:
;; Draw the tree illustrating the process generated by the count-change procedure of
;; Section 1.2.2 in making change for 11 cents. What are the orders of growth of the
;; space and number of steps used by this process as the amount to be changed increases?

; 
; 
;                                  11 => 50 25 10 5 1
;                                        4|0
;                              +----------+---------+
;                              |                    |
;                         11 => 25 10 5 1      -39 => 50 25 10 5 1
;                             4|0
;                     +--------+-------+
;                     |                |
;                11 => 10 5 1    -14 => 25 10 5 1
;                    3|1
;             +-------+--------------------------------------+
;             |                                              |
;       11 => 5 1                                       1=> 10 5 1
;            1|2                                            1|0
;     +-------+-------+                                 +----+---------+
;     |               |                                 |              |
;  11=> 1          6 => 5 1                           1=> 5 1      -9 => 10 5 1
;                    1|1                               1|0
;            +--------+----+                      +-----+---+
;            |             |                      |         |
;         6 => 1        1 => 5 1               1 => 1     -4=> 5 1
;                         1|0
;                     +----+----+
;                     |         |
;                 1 => 1     -4=> 5 1


;; Space increment: O(n)
;; Step  increment: O(n^5)

;; Excercise 1.15:
;; The sine of an angle (specified in radians) can be computed by making use
;; of the approximation sin x ≈ x if x is sufficiently small,
;; and the trigonometric identity:
;  sin x = 3sin(x/3) - 4sin^3(x/3)


;; to reduce thesize of the argument of sin.
;; (For purposes of this exercise an angle is considered "sufficiently small"
;; if its magnitude is not greater than 0.1 radians.)
;; These ideas are incorporated in the following procedures:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

;; a) How many times is the procedure p applied when (sine 12.15) is evaluated?
;; b) What is the order of growth in space and number of steps (as a function of a)
;;    uesd by the process generated by the sine procedure when (sine a) is evaluated?

;; a) 5 times
;; b) 0.1 * 3^x = n (x is the step we used)
;;    transformat: x = log3(10n)
;;    so: both step and space are in order of O(log(n))

;; Excercise 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 (b^(n/2))^2 = (b^2)^(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 abn 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.)

(define (fast-expt b n)
  (define (square x) (* x x))
    (define fast-expt-iter
      (lambda (N B product)
        (cond [(= N 0) product]
              [(even? N)
               (fast-expt-iter (/ N 2) (square B) product)]
              [else
               (fast-expt-iter (- N 1) B (* B product))]
              )))
  (fast-expt-iter n b 1))


;; 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 (mult a b)
  (if (= b 0)
      0
      (+ a (mult 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)
  (define halve (lambda (x) (/ x 2)))
  (define double (lambda (x) (* x 2)))
  (cond [(= 0 b) 0]
        [(even? b) (double (fast-mult a (halve b)))]
        [else
         (+ a (fast-mult a (- b 1)))]))

;; Excercise 1.18:
;; Using the results of Exercise 1.16 and Exercise 1.17,
;; devise a procedure that generates an iterative process for multiplying
;; two integers in terms of adding, doubling, and halving and uses
;; a logarithmic number of steps

(define (fast-mult-iter a b)
  (define halve (lambda (x) (/ x 2)))
  (define double (lambda (x) (* x 2)))
  (define (helper A B product)
    (cond [(= B 0) product]
          [(even? B) (helper (double A) (halve B) product)]
          [else
           (helper A (- B 1) (+ product A))]))
  (helper a b 0))

;; Excercise 1.19:
;; There is a clever algorithm for computing the
;; Fibonacci numbers in a logarithmic number of steps. Recall the
;; transformation of the state variables a and b in the fib-iter
;; process of Section 1.2.2: a à a + b and b à a. Call this
;; transformation T , and observe that applying T over and over
;; again n times, starting with 1 and 0, produces the pair Fib(n + 1)
;; and Fib(n). In other words, the Fibonacci numbers are produced
;; by applying T n, the nth power of the transformation T , starting
;; with the pair (1, 0). Now consider T to be the special case of
;; p = 0 and q = 1 in a family of transformations Tpq, where Tpq
;; transforms the pair (a, b) according to a à bq + aq + ap and
;; b à bp + aq. Show that if we apply such a transformation Tpq
;; twice, the effect is the same as using a single transformation Tp0q0
;; of the same form, and compute p0 and q0 in terms of p and q.
;; This gives us an explicit way to square these transformations,
;; and thus we can compute T n using successive squaring, as in
;; the fast-expt procedure. Put this all together to complete the
;; following procedure, which runs in a logarithmic number of
;; steps

; 
; (define (fib n)
;   (fib-iter 1 0 0 1 n))
; (define (fib-iter a b p q count)
;   (cond ((= count 0) b)
;         ((even? count)
;          (fib-iter a
;                    b
;                    <??> ; compute p’
;                    <??> ; compute q’
;                    (/ count 2)))
;         (else (fib-iter (+ (* b q) (* a q) (* a p))
;                         (+ (* b p) (* a q))
;                         p
;                         q
;                         (- count 1)))))


(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (define (square x) (* x x))
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (* 2 p q) (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))