src/sicp/ex1_15.clj

   1 (ns sicp.ex1_15
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.15: sin (x) calculation
   6 ;;    a.  How many times is the procedure p applied when (sine 12.15)
   7 ;;        is evaluated?
   8 ;;    b.  What is the order of growth in space and number of steps (as
   9 ;;        a function of a) used by the process generated by the sine
  10 ;;        procedure when (sine a) is evaluated?
  11 (defn p [x] (- (* 3 x) (* 4 (cube x))))
  12
  13 (defn sine [angle]
  14   (if (not (> (myabs angle) 0.1))
  15     angle
  16     (p (sine (/ angle 3.0)))))
  17
  18 ;; solution to (a) => 5
  19 ;; (comment
  20 ;; user> (dotrace [p] (sine 12.15))
  21 ;; TRACE t2490: (p 0.049999999999999996)
  22 ;; TRACE t2490: => 0.1495
  23 ;; TRACE t2491: (p 0.1495)
  24 ;; TRACE t2491: => 0.4351345505
  25 ;; TRACE t2492: (p 0.4351345505)
  26 ;; TRACE t2492: => 0.9758465331678772
  27 ;; TRACE t2493: (p 0.9758465331678772)
  28 ;; TRACE t2493: => -0.7895631144708228
  29 ;; TRACE t2494: (p -0.7895631144708228)
  30 ;; TRACE t2494: => -0.39980345741334
  31 ;; -0.39980345741334
  32 ;; )
  33
  34 ;; solution to b
  35 ;; both space and number of steps grows as log3(a) -> log a to the base 3.
  36 ;;
  37 ;; proof:
  38 ;;   a * (1/3)^n <= 0.1
  39 ;;   => take log to the base 3 on both the sides.
  40
  41 ;; Note: Finding the order of space in a recursive process is sort of, equiv
  42 ;;       to finding the number of deferred operations. Which is in-turn the
  43 ;;       same as the depth of the evaluation tree.