src/main/clojure/sicp/ch1_2.clj

   1 (ns sicp.chapter1.ch1_2
   2   (:use (clojure.contrib trace math)))
   3
   4
   5 (defn factorial [n]
   6   (if (= n 1)
   7     1
   8     (* n (factorial (- n 1)))))
   9
  10 ;; stack friendly version
  11 (defn factorial2 [n]
  12   (loop [x n acc 1]
  13     (if (= x 1)
  14       acc
  15       (recur (- x 1) (* acc x)))))
  16
  17 ;; even better
  18 (defn factorial3 [n]
  19   (reduce * (range 1 (inc n))))
  20
  21 (comment
  22  user> (dotrace [factorial] (factorial 3))
  23  TRACE t2701: (factorial 3)
  24  TRACE t2702: |    (factorial 2)
  25  TRACE t2703: |    |    (factorial 1)
  26  TRACE t2703: |    |    => 1
  27  TRACE t2702: |    => 2
  28  TRACE t2701: => 6
  29  6
  30 )
  31
  32 (comment
  33   sicp.chapter1.ch1_2> (dotrace [factorial] (factorial 6))
  34   TRACE t2778: (factorial 6)
  35   TRACE t2779: |    (factorial 5)
  36   TRACE t2780: |    |    (factorial 4)
  37   TRACE t2781: |    |    |    (factorial 3)
  38   TRACE t2782: |    |    |    |    (factorial 2)
  39   TRACE t2783: |    |    |    |    |    (factorial 1)
  40   TRACE t2783: |    |    |    |    |    => 1
  41   TRACE t2782: |    |    |    |    => 2
  42   TRACE t2781: |    |    |    => 6
  43   TRACE t2780: |    |    => 24
  44   TRACE t2779: |    => 120
  45   TRACE t2778: => 720
  46   720
  47   )
  48
  49 (comment
  50   sicp.chapter1.ch1_2> (dotrace [factorial2] (factorial2 6))
  51   TRACE t2806: (factorial2 6)
  52   TRACE t2806: => 720
  53   720
  54   )
  55
  56 (defn fact-iter [product counter max-count]
  57   (if (> counter max-count)
  58     product
  59     (fact-iter (* product counter)
  60                (inc counter)
  61                max-count)))
  62
  63 (defn factorial [n]
  64   (fact-iter 1 1 n))
  65
  66 (comment
  67 user> (dotrace [factorial fact-iter] (factorial 6))
  68 TRACE t2378: (factorial 6)
  69 TRACE t2379: |    (fact-iter 1 1 6)
  70 TRACE t2380: |    |    (fact-iter 1 2 6)
  71 TRACE t2381: |    |    |    (fact-iter 2 3 6)
  72 TRACE t2382: |    |    |    |    (fact-iter 6 4 6)
  73 TRACE t2383: |    |    |    |    |    (fact-iter 24 5 6)
  74 TRACE t2384: |    |    |    |    |    |    (fact-iter 120 6 6)
  75 TRACE t2385: |    |    |    |    |    |    |    (fact-iter 720 7 6)
  76 TRACE t2385: |    |    |    |    |    |    |    => 720
  77 TRACE t2384: |    |    |    |    |    |    => 720
  78 TRACE t2383: |    |    |    |    |    => 720
  79 TRACE t2382: |    |    |    |    => 720
  80 TRACE t2381: |    |    |    => 720
  81 TRACE t2380: |    |    => 720
  82 TRACE t2379: |    => 720
  83 TRACE t2378: => 720
  84 720
  85 )
  86
  87 ;; observation: clojure loop-recur construct is essentially the same as
  88 ;; the iterative version.
  89
  90 ;; exercise 1.9
  91 (defn ++ [a b]
  92   (if (= a 0)
  93     b
  94     (inc (++ (dec a) b))))
  95
  96 (comment
  97   This version is a recursive process, where the previous call increments
  98   the sum by 1 and each call decrement the first operand by 1.
  99
 100 user> (dotrace [++] (++ 4 5))
 101 TRACE t3745: (++ 4 5)
 102 TRACE t3746: |    (++ 3 5)
 103 TRACE t3747: |    |    (++ 2 5)
 104 TRACE t3748: |    |    |    (++ 1 5)
 105 TRACE t3749: |    |    |    |    (++ 0 5)
 106 TRACE t3749: |    |    |    |    => 5
 107 TRACE t3748: |    |    |    => 6
 108 TRACE t3747: |    |    => 7
 109 TRACE t3746: |    => 8
 110 TRACE t3745: => 9
 111 9
 112 )
 113 (defn ++ [a b]
 114   (if (= a 0)
 115     b
 116     (++ (dec a) (inc b))))
 117
 118 (comment
 119
 120 user> (dotrace [++] (++ 4 5))
 121 TRACE t3766: (++ 4 5)
 122 TRACE t3767: |    (++ 3 6)
 123 TRACE t3768: |    |    (++ 2 7)
 124 TRACE t3769: |    |    |    (++ 1 8)
 125 TRACE t3770: |    |    |    |    (++ 0 9)
 126 TRACE t3770: |    |    |    |    => 9
 127 TRACE t3769: |    |    |    => 9
 128 TRACE t3768: |    |    => 9
 129 TRACE t3767: |    => 9
 130 TRACE t3766: => 9
 131 9
 132 )
 133
 134 ;; exercise 1.10
 135 ;; ackerman functions
 136 (defn A [x y]
 137   (cond (= y 0) 0
 138         (= x 0) (* 2 y)
 139         (= y 1) 2
 140         :else (A (- x 1)
 141                  (A x (- y 1)))))
 142
 143 (comment
 144 user> (A 1 10)
 145 1024
 146 user> (A 2 4)
 147 65536
 148 user> (A 3 3)
 149 65536
 150 )
 151
 152 (defn f [n] (A 0 n)) ; f(n) = 2n
 153 (defn g [n] (A 1 n)) ; g(n) = 2^n
 154 (comment
 155   g (n) = A (1,n)
 156         = A (0, A (1, n-1)) = f (A(1,n-1))
 157           = f (f (1,n-2))
 158             .....
 159             = f (f (f ... f (1,(n- (n-1)))))
 160               = f (f (f ... 2))
 161                 = 2 * (2^(n-1))
 162                   = 2^n
 163 )
 164
 165 (defn h [n] (A 2 n)) ; h(n) = 2^(n^2)
 166
 167 ;; section 1.2.2: Tree Recursion
 168 (defn fib [n]
 169   (cond (= n 0) 0
 170         (= n 1) 1
 171         :else (+ (fib (- n 1))
 172                  (fib (- n 2)))))
 173
 174 ;; iterative version
 175 (defn fib [n]
 176   (fib-iter 1 0 n))
 177
 178 (defn fib-iter [a b count]
 179   (if (= count 0)
 180     b
 181     (fib-iter (+ a b) a (dec count))))
 182
 183 ;; example: counting changes
 184 (defn count-change [amount]
 185   (cc amount 5))
 186
 187 (defn cc [amount kinds-of-coins]
 188   (cond (= amount 0) 1
 189         (or (< amount 0) (= kinds-of-coins 0)) 0
 190         :else (+ (cc amount (- kinds-of-coins 1))
 191                  (cc (- amount
 192                         (first-denomination kinds-of-coins))
 193                      kinds-of-coins))))
 194
 195 (defn first-denomination [kinds-of-coins]
 196   (cond (= kinds-of-coins 1) 1
 197         (= kinds-of-coins 2) 5
 198         (= kinds-of-coins 3) 10
 199         (= kinds-of-coins 4) 25
 200         (= kinds-of-coins 5) 50))
 201
 202 (defn first-denomination [kinds-of-coins]
 203   ({1 1 2 5 3 10 4 25 5 50} kinds-of-coins))
 204
 205 ;; exercise 1.11: A function f is defined by the rule that f(n) = n if n < 3
 206 ;;                and f(n) = f(n - 1) + 2f(n  - 2) + 3f(n - 3) if n> 3.
 207 ;;                Write a procedure that computes f by means of a recursive
 208 ;;                process. Write a procedure that computes f by means of an
 209 ;;                iterative process.
 210 (defn f [n]
 211   (if (< n 3)
 212     n
 213     (+ (f (- n 1))
 214        (* 2 (f (- n 2)))
 215        (* 3 (f (- n 3))))))
 216
 217 (comment
 218 user> (map f (range 10))
 219 (0 1 2 4 11 25 59 142 335 796)
 220 )
 221
 222 ;; ex 1.11: iterative version
 223 (defn f [n]
 224   (if (< n 3)
 225     n
 226     (f-iter n 2 1 0)))
 227
 228 (defn f-iter [count prev0 prev1 prev2]
 229   (if (= count 3)
 230     (+ prev0
 231        (* 2 prev1)
 232        (* 3 prev2))
 233     (f-iter (dec count)
 234             (+ prev0
 235                (* 2 prev1)
 236                (* 3 prev2))
 237             prev0
 238             prev1)))
 239
 240 ;; ex 1.11: iterative version with let
 241 (defn f-iter [count prev0 prev1 prev2]
 242   (let [res (+ prev0 (* 2 prev1) (* 3 prev2))]
 243     (if (= count 3)
 244       res
 245       (f-iter (dec count)
 246               res
 247               prev0
 248               prev1))))
 249
 250 ;; exercise 1.12.  The following pattern of numbers is called Pascal's triangle.
 251 ;;          1
 252 ;;        1   1
 253 ;;      1   2   1
 254 ;;    1   3   3   1
 255 ;;  1   4   6   4   1
 256 ;; ...................
 257 ;;
 258 ;;                 The numbers at the edge of the triangle are all 1, and each
 259 ;;                 number inside the triangle is the sum of the two numbers above
 260 ;;                 it. Write a procedure that computes elements of Pascal's triangle
 261 ;;                 by means of a recursive process.
 262 (defn pascal [row col]
 263   (when (<= col row)
 264     (if (or (= col 0) (= row col))
 265       1
 266       (+ (pascal (dec row) col)
 267          (pascal (dec row) (dec col))))))
 268
 269 ;; exercise 1.13:
 270 (comment
 271 See the pdfs in the directory for the answers.
 272 )
 273
 274 ;; ex 1.13 (contd)
 275 (defn fib-approx [n]
 276   (let [phi (/ (+ 1 (sqrt 5)) 2)]
 277     (/ (expt phi n) (sqrt 5))))
 278
 279 (comment
 280 user> (map fib-approx (range 10))
 281 (0.4472135954999579 0.7236067977499789 1.1708203932499368 1.8944271909999157 3.065247584249853 4.959674775249769 8.024922359499623 12.984597134749393 21.009519494249016 33.99411662899841)
 282 )
 283
 284 ;; exercise 1.14: tree of (count-changes 11)
 285 (comment
 286   See the pdf for the tree representation.
 287 )
 288
 289
 290 ;; order of size and computation
 291 ;; see PDF, but below is the trace tree.
 292 (comment
 293 user> (use 'clojure.contrib.trace)
 294 nil
 295 user> (dotrace [count-change cc] (count-change 11))
 296 TRACE t2609: (count-change 11)
 297 TRACE t2610: |    (cc 11 5)
 298 TRACE t2611: |    |    (cc 11 4)
 299 TRACE t2612: |    |    |    (cc 11 3)
 300 TRACE t2613: |    |    |    |    (cc 11 2)
 301 TRACE t2614: |    |    |    |    |    (cc 11 1)
 302 TRACE t2615: |    |    |    |    |    |    (cc 11 0)
 303 TRACE t2615: |    |    |    |    |    |    => 0
 304 TRACE t2616: |    |    |    |    |    |    (cc 10 1)
 305 TRACE t2617: |    |    |    |    |    |    |    (cc 10 0)
 306 TRACE t2617: |    |    |    |    |    |    |    => 0
 307 TRACE t2618: |    |    |    |    |    |    |    (cc 9 1)
 308 TRACE t2619: |    |    |    |    |    |    |    |    (cc 9 0)
 309 TRACE t2619: |    |    |    |    |    |    |    |    => 0
 310 TRACE t2620: |    |    |    |    |    |    |    |    (cc 8 1)
 311 TRACE t2621: |    |    |    |    |    |    |    |    |    (cc 8 0)
 312 TRACE t2621: |    |    |    |    |    |    |    |    |    => 0
 313 TRACE t2622: |    |    |    |    |    |    |    |    |    (cc 7 1)
 314 TRACE t2623: |    |    |    |    |    |    |    |    |    |    (cc 7 0)
 315 TRACE t2623: |    |    |    |    |    |    |    |    |    |    => 0
 316 TRACE t2624: |    |    |    |    |    |    |    |    |    |    (cc 6 1)
 317 TRACE t2625: |    |    |    |    |    |    |    |    |    |    |    (cc 6 0)
 318 TRACE t2625: |    |    |    |    |    |    |    |    |    |    |    => 0
 319 TRACE t2626: |    |    |    |    |    |    |    |    |    |    |    (cc 5 1)
 320 TRACE t2627: |    |    |    |    |    |    |    |    |    |    |    |    (cc 5 0)
 321 TRACE t2627: |    |    |    |    |    |    |    |    |    |    |    |    => 0
 322 TRACE t2628: |    |    |    |    |    |    |    |    |    |    |    |    (cc 4 1)
 323 TRACE t2629: |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 4 0)
 324 TRACE t2629: |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
 325 TRACE t2630: |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 3 1)
 326 TRACE t2631: |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 3 0)
 327 TRACE t2631: |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
 328 TRACE t2632: |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 2 1)
 329 TRACE t2633: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 2 0)
 330 TRACE t2633: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
 331 TRACE t2634: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 1)
 332 TRACE t2635: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 0)
 333 TRACE t2635: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 0
 334 TRACE t2636: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    (cc 0 1)
 335 TRACE t2636: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
 336 TRACE t2634: |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
 337 TRACE t2632: |    |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
 338 TRACE t2630: |    |    |    |    |    |    |    |    |    |    |    |    |    => 1
 339 TRACE t2628: |    |    |    |    |    |    |    |    |    |    |    |    => 1
 340 TRACE t2626: |    |    |    |    |    |    |    |    |    |    |    => 1
 341 TRACE t2624: |    |    |    |    |    |    |    |    |    |    => 1
 342 TRACE t2622: |    |    |    |    |    |    |    |    |    => 1
 343 TRACE t2620: |    |    |    |    |    |    |    |    => 1
 344 TRACE t2618: |    |    |    |    |    |    |    => 1
 345 TRACE t2616: |    |    |    |    |    |    => 1
 346 TRACE t2614: |    |    |    |    |    => 1
 347 TRACE t2637: |    |    |    |    |    (cc 6 2)
 348 TRACE t2638: |    |    |    |    |    |    (cc 6 1)
 349 TRACE t2639: |    |    |    |    |    |    |    (cc 6 0)
 350 TRACE t2639: |    |    |    |    |    |    |    => 0
 351 TRACE t2640: |    |    |    |    |    |    |    (cc 5 1)
 352 TRACE t2641: |    |    |    |    |    |    |    |    (cc 5 0)
 353 TRACE t2641: |    |    |    |    |    |    |    |    => 0
 354 TRACE t2642: |    |    |    |    |    |    |    |    (cc 4 1)
 355 TRACE t2643: |    |    |    |    |    |    |    |    |    (cc 4 0)
 356 TRACE t2643: |    |    |    |    |    |    |    |    |    => 0
 357 TRACE t2644: |    |    |    |    |    |    |    |    |    (cc 3 1)
 358 TRACE t2645: |    |    |    |    |    |    |    |    |    |    (cc 3 0)
 359 TRACE t2645: |    |    |    |    |    |    |    |    |    |    => 0
 360 TRACE t2646: |    |    |    |    |    |    |    |    |    |    (cc 2 1)
 361 TRACE t2647: |    |    |    |    |    |    |    |    |    |    |    (cc 2 0)
 362 TRACE t2647: |    |    |    |    |    |    |    |    |    |    |    => 0
 363 TRACE t2648: |    |    |    |    |    |    |    |    |    |    |    (cc 1 1)
 364 TRACE t2649: |    |    |    |    |    |    |    |    |    |    |    |    (cc 1 0)
 365 TRACE t2649: |    |    |    |    |    |    |    |    |    |    |    |    => 0
 366 TRACE t2650: |    |    |    |    |    |    |    |    |    |    |    |    (cc 0 1)
 367 TRACE t2650: |    |    |    |    |    |    |    |    |    |    |    |    => 1
 368 TRACE t2648: |    |    |    |    |    |    |    |    |    |    |    => 1
 369 TRACE t2646: |    |    |    |    |    |    |    |    |    |    => 1
 370 TRACE t2644: |    |    |    |    |    |    |    |    |    => 1
 371 TRACE t2642: |    |    |    |    |    |    |    |    => 1
 372 TRACE t2640: |    |    |    |    |    |    |    => 1
 373 TRACE t2638: |    |    |    |    |    |    => 1
 374 TRACE t2651: |    |    |    |    |    |    (cc 1 2)
 375 TRACE t2652: |    |    |    |    |    |    |    (cc 1 1)
 376 TRACE t2653: |    |    |    |    |    |    |    |    (cc 1 0)
 377 TRACE t2653: |    |    |    |    |    |    |    |    => 0
 378 TRACE t2654: |    |    |    |    |    |    |    |    (cc 0 1)
 379 TRACE t2654: |    |    |    |    |    |    |    |    => 1
 380 TRACE t2652: |    |    |    |    |    |    |    => 1
 381 TRACE t2655: |    |    |    |    |    |    |    (cc -4 2)
 382 TRACE t2655: |    |    |    |    |    |    |    => 0
 383 TRACE t2651: |    |    |    |    |    |    => 1
 384 TRACE t2637: |    |    |    |    |    => 2
 385 TRACE t2613: |    |    |    |    => 3
 386 TRACE t2656: |    |    |    |    (cc 1 3)
 387 TRACE t2657: |    |    |    |    |    (cc 1 2)
 388 TRACE t2658: |    |    |    |    |    |    (cc 1 1)
 389 TRACE t2659: |    |    |    |    |    |    |    (cc 1 0)
 390 TRACE t2659: |    |    |    |    |    |    |    => 0
 391 TRACE t2660: |    |    |    |    |    |    |    (cc 0 1)
 392 TRACE t2660: |    |    |    |    |    |    |    => 1
 393 TRACE t2658: |    |    |    |    |    |    => 1
 394 TRACE t2661: |    |    |    |    |    |    (cc -4 2)
 395 TRACE t2661: |    |    |    |    |    |    => 0
 396 TRACE t2657: |    |    |    |    |    => 1
 397 TRACE t2662: |    |    |    |    |    (cc -9 3)
 398 TRACE t2662: |    |    |    |    |    => 0
 399 TRACE t2656: |    |    |    |    => 1
 400 TRACE t2612: |    |    |    => 4
 401 TRACE t2663: |    |    |    (cc -14 4)
 402 TRACE t2663: |    |    |    => 0
 403 TRACE t2611: |    |    => 4
 404 TRACE t2664: |    |    (cc -39 5)
 405 TRACE t2664: |    |    => 0
 406 TRACE t2610: |    => 4
 407 TRACE t2609: => 4
 408 4
 409 )
 410 ;; TODO: orders of growth in space and number of steps.
 411
 412
 413 ;; exercise 1.15: sin (x) calculation
 414 ;;    a.  How many times is the procedure p applied when (sine 12.15)
 415 ;;        is evaluated?
 416 ;;    b.  What is the order of growth in space and number of steps (as
 417 ;;        a function of a) used by the process generated by the sine
 418 ;;        procedure when (sine a) is evaluated?
 419 (defn cube [x] (* x x x))
 420
 421 (defn p [x] (- (* 3 x) (* 4 (cube x))))
 422
 423 (defn sine [angle]
 424   (if (not (> (abs angle) 0.1))
 425     angle
 426     (p (sine (/ angle 3.0)))))
 427
 428 ;; solution to (a) => 5
 429 (comment
 430 user> (dotrace [p] (sine 12.15))
 431 TRACE t2490: (p 0.049999999999999996)
 432 TRACE t2490: => 0.1495
 433 TRACE t2491: (p 0.1495)
 434 TRACE t2491: => 0.4351345505
 435 TRACE t2492: (p 0.4351345505)
 436 TRACE t2492: => 0.9758465331678772
 437 TRACE t2493: (p 0.9758465331678772)
 438 TRACE t2493: => -0.7895631144708228
 439 TRACE t2494: (p -0.7895631144708228)
 440 TRACE t2494: => -0.39980345741334
 441 -0.39980345741334
 442 )
 443
 444 ;; solution to b
 445 ;; both space and number of steps grows as log3(a) -> log a to the base 3.
 446 ;;
 447 ;; proof:
 448 ;;   a * (1/3)^n <= 0.1
 449 ;;   => take log to the base 3 on both the sides.
 450
 451 ;; Note: Finding the order of space in a recursive process is sort of, equiv
 452 ;;       to finding the number of deferred operations. Which is in-turn the
 453 ;;       same as the depth of the evaluation tree.
 454
 455 ;; 1.2.4: exponentiation
 456 ;; computing b^n
 457 (defn expt [b n]
 458   (if (= n 0)
 459     1
 460     (* b (expt b (dec n)))))
 461
 462 ;; iterative
 463 (defn expt [b n]
 464   (expt-iter b n 1))
 465
 466 (defn expt-iter [base counter product]
 467   (if (= counter 0)
 468     product
 469     (expt-iter b
 470                (dec counter)
 471                (* product base))))
 472
 473 ;; fast version
 474 (defn fast-expt [b n]
 475   (cond (= n 0) 1
 476         (even? n) (square (fast-expt b (/ n 2)))
 477         :else (* b (fast-expt b (dec n)))))
 478
 479 (defn even? [x]
 480   (= (rem x 2) 0))
 481
 482 (defn square [x]
 483   (* x x))
 484
 485 ;; exercise 1.16:
 486 (defn expt [b n]
 487   (expt-iter b n 1))
 488
 489 (defn expt-iter [b n a]
 490   (cond (= n 0) a
 491         (even? n) (expt-iter (square b) (/ n 2) a)
 492         :else (expt-iter b (- n 1) (* a b))))
 493
 494 ;; exercise 1.17:
 495 (defn mult [a b]
 496   (if (= b 0)
 497     0
 498     (+ a (mult a (- b 1)))))
 499
 500 ;; product = 2 * (a * (b/2)) for even b
 501 ;;         = a    + (a * (b - 1)) for odd b
 502 (defn fast-mult [a b]
 503   (cond (= b 0) 0
 504         (= b 1) a
 505         (even? b) (twice (fast-mult a (half b)))
 506         :else (+ a (fast-mult a (- b 1)))))
 507
 508 ;; double
 509 (defn twice [x]
 510   (* 2 x))
 511
 512 (defn half [x]
 513   (/ x 2))
 514
 515 ;; exercise 1.18: iterative multiply thru addition
 516 ;; the idea is to keep a state variable.
 517 (defn fast-mult-new [a b]
 518   (fast-mult-iter a b 0))
 519
 520 (defn fast-mult-iter [a b k]
 521   (cond (= b 0) k
 522         (even? b) (fast-mult-iter (twice a) (half b) k)
 523         :else (fast-mult-iter a (- b 1) (+ k a))))
 524
 525 (comment
 526 user> (dotrace [fast-mult-new fast-mult-iter] (fast-mult-new 2 3))
 527 TRACE t2915: (fast-mult-new 2 3)
 528 TRACE t2916: |    (fast-mult-iter 2 3 0)
 529 TRACE t2917: |    |    (fast-mult-iter 2 2 2)
 530 TRACE t2918: |    |    |    (fast-mult-iter 4 1 2)
 531 TRACE t2919: |    |    |    |    (fast-mult-iter 4 0 6)
 532 TRACE t2919: |    |    |    |    => 6
 533 TRACE t2918: |    |    |    => 6
 534 TRACE t2917: |    |    => 6
 535 TRACE t2916: |    => 6
 536 TRACE t2915: => 6
 537 6
 538 )
 539
 540 ;; exercise 1.19: fast fibonacci
 541 ;; see the pdf of the notebook scan for the derivation of p' and q'
 542 (defn ffib [n]
 543   (ffib-iter 1 0 0 1 n))
 544
 545 (defn ffib-iter [a b p q count]
 546   (cond (= count 0) b
 547         (even? count)
 548         (ffib-iter a
 549                    b
 550                    (+ (* p p) (* q q))
 551                    (+ (* 2 p q) (* q q))
 552                    (/ count 2))
 553         :else (ffib-iter (+ (* b q) (* a q) (* a p))
 554                          (+ (* b p) (* a q))
 555                          p
 556                          q
 557                          (- count 1))))