src/sicp/ex1_36.clj

   1 ;; Exercise 1.36.  Modify fixed-point so that it prints the sequence
   2 ;; of approximations it generates, using the newline and display
   3 ;; primitives shown in exercise 1.22. Then find a solution to
   4 ;; x^x = 1000
   5 ;; by finding a fixed point of x |->  log(1000)/log(x).
   6 ;;
   7 ;; Compare the number of steps this takes with and without average damping.
   8 (ns sicp.ex1_36
   9   (:use [sicp utils]
  10         [clojure.contrib test-is]))
  11
  12 (defn close-enough? [x y tolerance]
  13   (< (abs (- x y)) tolerance))
  14
  15 (defn fixed-point [f guess]
  16   (let [next (f guess)
  17         nsteps 0]
  18     (do
  19       (println "new guess is " next)
  20       (if (close-enough? next guess 0.00001)
  21         next
  22         (fixed-point f next)))))
  23
  24 ;; fixed point
  25 (comment
  26 (fixed-point #(/ (Math/log 1000) (Math/log %)) 1.1)
  27 new guess is  72.47657378429035
  28 new guess is  1.6127318474109593
  29 new guess is  14.45350138636525
  30 new guess is  2.5862669415385087
  31 new guess is  7.269672273367045
  32 new guess is  3.4822383620848467
  33 new guess is  5.536500810236703
  34 new guess is  4.036406406288111
  35 new guess is  4.95053682041456
  36 new guess is  4.318707390180805
  37 new guess is  4.721778787145103
  38 new guess is  4.450341068884912
  39 new guess is  4.626821434106115
  40 new guess is  4.509360945293209
  41 new guess is  4.586349500915509
  42 new guess is  4.535372639594589
  43 new guess is  4.568901484845316
  44 new guess is  4.546751100777536
  45 new guess is  4.561341971741742
  46 new guess is  4.551712230641226
  47 new guess is  4.558059671677587
  48 new guess is  4.55387226495538
  49 new guess is  4.556633177654167
  50 new guess is  4.554812144696459
  51 new guess is  4.556012967736543
  52 new guess is  4.555220997683307
  53 new guess is  4.555743265552239
  54 new guess is  4.555398830243649
  55 new guess is  4.555625974816275
  56 new guess is  4.555476175432173
  57 new guess is  4.555574964557791
  58 new guess is  4.555509814636753
  59 new guess is  4.555552779647764
  60 new guess is  4.555524444961165
  61 new guess is  4.555543131130589
  62 new guess is  4.555530807938518
  63 new guess is  4.555538934848503
  64 ;; => 4.555538934848503
  65 )
  66
  67 ;; with average damping
  68 (comment
  69 (defn average [x y] (/ (+ x y) 2.0))
  70 (fixed-point #(average % (/ (Math/log 1000) (Math/log %))) 1.1)
  71 new guess is  36.78828689214517
  72 new guess is  19.352175531882512
  73 new guess is  10.84183367957568
  74 new guess is  6.870048352141772
  75 new guess is  5.227224961967156
  76 new guess is  4.701960195159289
  77 new guess is  4.582196773201124
  78 new guess is  4.560134229703681
  79 new guess is  4.5563204194309606
  80 new guess is  4.555669361784037
  81 new guess is  4.555558462975639
  82 new guess is  4.55553957996306
  83 new guess is  4.555536364911781
  84 ;; => 4.555536364911781
  85 )
  86
  87 (comment
  88 "As we can see, average damping significantly reduces the number of steps."
  89 )