1.2 Procedures and the Process They Generate
============================================

Exercise 1.9
------------

The first procedure is recursive:

.. code-block:: scheme

    (+ 4 5)
    (inc (+ 3 5))
    (inc (inc (+ 2 5)))
    (inc (inc (inc (+ 1 5))))
    (inc (inc (inc (inc (+ 0 5)))))
    (inc (inc (inc (inc 5))))
    (int (inc (inc 6)))
    (inc (inc 7))
    (inc 8)
    9


The second procedure is iterative:

.. code-block:: scheme

    (+ 4 5)
    (+ 3 6)
    (+ 2 7)
    (+ 1 8)
    (+ 0 9)
    9


Exercise 1.10
-------------

.. code-block:: scheme

    1 ]=> (A 1 10)

    ;Value: 1024

    1 ]=> (A 2 4)

    ;Value: 65536

    1 ]=> (A 3 3)

    ;Value: 65536

The concise mathematical definitions for the functions computed by the
procedures ``f``, ``g``, and ``h`` for positive integer values of :math:`n`:

.. math::

    f = 2n

    g = 2^n

    h = 2^{2^{n}}

    k = 5n^2


Exercise 1.11
-------------

Recursive:

.. code-block:: scheme

    (define (f n)
      (cond ((< n 3) n)
            (else (+ (f (- n 1))
                     (* 2 (f (- n 2)))
                     (* 3 (f (- n 3)))))))

Iterative:

.. code-block:: scheme

    (define (f n)
      (define (f-iter count a b c)
      (if (< count 0)
          a
          (f-iter (- count 1)
                  (+ a (* 2 b) (* 3 c))
                  a
                  b)))
      (if (< n 3)
          n
          (f-iter (- n 3) 2 1 0)))


Exercise 1.12
-------------
.. code-block:: scheme

    (define (pascal row col)
      (cond ((> col row)
             (error "invalid row-column"))
            ((or (= col 1) (= col row)) 1)
            (else (+ (pascal (- row 1) (- col 1))
                     (pascal (- row 1) col)))))


Exercise 1.13
-------------

Here is a well-explained proof_, by `Bill the Lizard`__.

.. _proof: http://www.billthelizard.com/2009/12/sicp-exercise-113-fibonacci-and-golden.html

.. __: http://www.billthelizard.com/


Exercise 1.14
-------------

The order of growth of the space is :math:`O(a)`.

The order of growth of the number of steps is :math:`O(n^2)`.


Exercise 1.15
-------------

The expression ``(sine 12.15)`` is expanded as follows:

.. code-block:: scheme

    (sine 12.15)
    (p (sine 4.05))
    (p (p (sine 1.35)))
    (p (p (p (sine 0.45))))
    (p (p (p (p (sine 0.15)))))
    (p (p (p (p (p (sine 0.05))))))
    (p (p (p (p (p 0.05)))))

As we can see, the procedure ``p`` us applied 5 times.

The angle ``a`` is divided by 3 each time the procedure ``p`` is applied.  For
an arbitrary ``a``, the number of steps ``n`` is the minimum value that
satisfy the following formula:

.. math::

    \frac{a}{3^{n - 1}} < 0.1

Therefore, the order of growth in space and number of steps are both
:math:`O(log{n})`.


Exercise 1.16
-------------

.. code-block:: scheme

    (define (expt b n)
      (define (expt-iter a b n)
        (cond ((= n 0) a)
              ((even? n) (expt-iter a
                                    (* b b)
                                    (/ n 2)))
              (else (expt-iter (* a b)
                               b
                               (- n 1)))))
      (expt-iter 1 b n))


Exercise 1.17
-------------

.. code-block:: scheme

    (define (* a b)
      (cond ((= b 0) 0)
            ((even? b) (double (* a (halve b))))
            (else (+ a (* a (- b 1))))))


Exercise 1.18
-------------

.. code-block:: scheme

    (define (* a b)
      (define (*-iter x a b)
        (cond ((= b 0) x)
              ((even? b) (*-iter x (double a) (halve b)))
              (else (*-iter (+ x a) a (- b 1)))))
      (*-iter 0 a b))


Exercise 1.19
-------------

The transformation :math:`T_{p\prime q\prime}` can be easily calculated
using matrix.

.. math::

    T_{pq} = \begin{bmatrix}q+p & q \\q & p \end{bmatrix}

    T_{p'q'}=T_{pq}^2=\begin{cases}
    a \leftarrow (q^2+2pq)b + (q^2 + 2pq)a + (p^2 + q^2)a \\
    \\
    b \leftarrow (p^2+q^2)b + (q^2 + 2pq)a
    \end{cases}

Therefore, :math:`p' = q^2 + p^2, q' = q^2 + 2pq`.

Our logarithmic Fibonacci procedure is as follows:

.. code-block:: scheme

    (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
                      (+ (* p p) (* q q))   ; compute p’
                      (+ (* q q) (* 2 p q)) ; compute q’
                      (/ count 2)))
            (else (fib-iter (+ (* b q) (* a q) (* a p))
                            (+ (* b p) (* a q))
                            p
                            q
                            (- count 1)))))


Exercise 1.20
-------------

The process of *normal-order* evaluation. It performs 18 ``remainder``
operations:

.. code-block:: scheme

    (gcd 206 40)

    (if (= 40 0) ...)

    (gcd 40 (remainder 206 40))

    (if (= (remainder 206 40) 0) ...)

    (if (= 6 0) ...)

    (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))

    (if (= (remainder 40 (remainder 206 40)) 0) ...)

    (if (= 4 0) ...)

    (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

    (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...)

    (if (= 2 0) ...)

    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

    (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...)

    (if (= 0 0) ...)
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

The process of *applicative-order* evaluation. It performs 4 ``remainder``
operations:

.. code-block:: scheme

    (gcd 206 40)

    (gcd 40 (remainder 206 40))

    (gcd 40 6)

    (gcd 6 (remainder 40 6))

    (gcd 6 4)

    (gcd 4 (remainder 6 4))

    (gcd 4 2)

    (gcd 2 (remainder 4 2))

    (gcd 2 0)

    2


Exercise 1.21
-------------

The ``smallest-divisor`` procedure:

.. code-block:: scheme

    (define (smallest-divisor n) (find-divisor n 2))
    (define (find-divisor n test-divisor)
      (define (square x) (* x x))
      (cond ((> (square test-divisor) n) n)
            ((divides? test-divisor n) test-divisor)
            (else (find-divisor n (+ test-divisor 1)))))
    (define (divides? a b) (= (remainder b a) 0))

Find the smallest divisor for thoese numbers:

.. code-block:: scheme

    > (smallest-divisor 199)
    199
    > (smallest-divisor 1999)
    1999
    > (smallest-divisor 19999)
    7


Exercise 1.22
-------------

The ``search-for-primes`` procedure:

.. code-block:: scheme

    (define (smallest-divisor n) (find-divisor n 2))
    (define (find-divisor n test-divisor)
      (define (square x) (* x x))
      (cond ((> (square test-divisor) n) n)
            ((divides? test-divisor n) test-divisor)
            (else (find-divisor n (+ test-divisor 1)))))
    (define (divides? a b) (= (remainder b a) 0))
    (define (prime? n)
      (= n (smallest-divisor n)))
    (define (timed-prime-test n)
      (start-prime-test n (runtime)))
    (define (start-prime-test n start-time)
      (if (prime? n)
          (report-prime n (- (runtime) start-time))))
    (define (report-prime n elapsed-time)
      (newline) (display n) (display " *** ") (display elapsed-time))

    (define (search-for-primes first last)
      (if (<= first last)
          (if (odd? first)
              (begin (timed-prime-test first)
                    (search-for-primes (+ first 1) last))
              (search-for-primes (+ first 1) last))))

Let's find the three smallest primes larger than 1000; larger than
10,000; larger than 100,000; larger than 1,000,000, respectively:

.. code-block:: scheme

    > (search-for-primes 1000 1019)

    1009 *** 15
    1013 *** 15
    1019 *** 15

    > (search-for-primes 10000 10037)

    10007 *** 47
    10009 *** 48
    10037 *** 46

    > (search-for-primes 100000 100043)

    100003 *** 150
    100019 *** 152
    100043 *** 149

    > (search-for-primes 1000000 1000037)

    1000003 *** 470
    1000033 *** 468
    1000037 *** 469

As is mentioned in Community-Scheme-Wiki_, computers today have become
too fast to appreciate the time required for primality test on those
small numbers. So we could perform tests with greater numbers (1e9
~ 1e12)to get meaningful results:

.. _Community-Scheme-Wiki: http://community.schemewiki.org/?sicp-ex-1.22

.. code-block:: scheme

    > (search-for-primes 1000000000 1000000021)

    1000000007 *** 14576
    1000000009 *** 15021
    1000000021 *** 13935

    > (search-for-primes 10000000000 10000000061)

    10000000019 *** 46108
    10000000033 *** 47346
    10000000061 *** 44855

    > (search-for-primes 100000000000 100000000057)

    100000000003 *** 146165
    100000000019 *** 150204
    100000000057 *** 143866

    > (search-for-primes 1000000000000 1000000000063)

    1000000000039 *** 472598
    1000000000061 *** 460440
    1000000000063 *** 474448

It can be easily observed that by increasing the tested number by
a magnitude, the required time increases by approximately a factor of
:math:`\sqrt{3}`. Therefore, the result is compatible with the notion
that programs run in a time proportional to the numbers of steps
required for the computation.


Exercise 1.23
-------------

The modified program is as follows:

.. code-block:: scheme

    (define (smallest-divisor n) (find-divisor n 2))
    (define (find-divisor n test-divisor)
      (define (square x) (* x x))
      (define (next n)
        (if (= n 2) 3 (+ n 2)))
      (cond ((> (square test-divisor) n) n)
            ((divides? test-divisor n) test-divisor)
            (else (find-divisor n (next test-divisor)))))
    (define (divides? a b) (= (remainder b a) 0))
    (define (prime? n)
      (= n (smallest-divisor n)))
    (define (timed-prime-test n)
      (start-prime-test n (runtime)))
    (define (start-prime-test n start-time)
      (if (prime? n)
          (report-prime n (- (runtime) start-time))))
    (define (report-prime n elapsed-time)
      (newline) (display n) (display " *** ") (display elapsed-time))

    (define (search-for-primes first last)
      (if (<= first last)
          (if (odd? first)
              (begin (timed-prime-test first)
                    (search-for-primes (+ first 1) last))
              (search-for-primes (+ first 1) last))))

Let's run those tests again:

.. code-block:: scheme

    > (search-for-primes 1000 1019)

    1009 *** 10
    1013 *** 10
    1019 *** 10

    > (search-for-primes 10000 10037)

    10007 *** 42
    10009 *** 31
    10037 *** 26

    > (search-for-primes 100000 100043)

    100003 *** 86
    100019 *** 80
    100043 *** 80

    > (search-for-primes 1000000 1000037)

    1000003 *** 339
    1000033 *** 268
    1000037 *** 268

    > (search-for-primes 1000000000 1000000021)

    1000000007 *** 8613
    1000000009 *** 8257
    1000000021 *** 16954

    > (search-for-primes 10000000000 10000000061)

    10000000019 *** 29032
    10000000033 *** 26263
    10000000061 *** 31629

    > (search-for-primes 100000000000 100000000057)

    100000000003 *** 88494
    100000000019 *** 85926
    100000000057 *** 82583

    > (search-for-primes 1000000000000 1000000000063)

    1000000000039 *** 266821
    1000000000061 *** 269202
    1000000000063 *** 278392

The observed ratio of the speeds of the two algorithms is between 1.5
and 2. I think this is because although the number of test steps is
halved, we are paying extra overhead for procedure ``next``. Compared
with the previous expression ``(+ test-divisor 1)``, which can be
highly-optimized to register increment machine code, the procedure
``next`` surely introduce overhead of branch and function call.


Exercise 1.24
-------------

The ``fast-prime?`` version:

.. code-block:: scheme

    (define (expmod base exp m)
      (define (square x) (* x x))
      (cond ((= exp 0)
            1)
            ((even? exp)
            (remainder
              (square
              (expmod base (/ exp 2) m))
              m))
            (else
            (remainder
              (* base
                (expmod base (- exp 1) m))
              m))))
    (define (fermat-test n)
      (define (try-it a)
        (= (expmod a n n) a))
      (try-it (+ 1 (random (- n 1)))))
    (define (fast-prime? n times)
      (cond ((= times 0) true)
            ((fermat-test n) (fast-prime? n (- times 1)))
            (else false)))
    (define (prime? n)
      (fast-prime? n 12))
    (define (timed-prime-test n)
      (start-prime-test n (runtime)))
    (define (start-prime-test n start-time)
      (if (prime? n)
          (report-prime n (- (runtime) start-time))))
    (define (report-prime n elapsed-time)
      (newline) (display n) (display " *** ") (display elapsed-time))

    (define (search-for-primes first last)
      (if (<= first last)
          (if (odd? first)
              (begin (timed-prime-test first)
                    (search-for-primes (+ first 1) last))
              (search-for-primes (+ first 1) last))))

    ;;; tests
    (timed-prime-test 1009)
    (timed-prime-test 1013)
    (timed-prime-test 1019)
    (timed-prime-test 10007)
    (timed-prime-test 10009)
    (timed-prime-test 10037)
    (timed-prime-test 100003)
    (timed-prime-test 100019)
    (timed-prime-test 100043)
    (timed-prime-test 1000003)
    (timed-prime-test 1000033)
    (timed-prime-test 1000037)

Test output:

.. code-block:: scheme

    1009 *** 119
    1013 *** 116
    1019 *** 115
    10007 *** 140
    10009 *** 164
    10037 *** 144
    100003 *** 161
    100019 *** 160
    100043 *** 161
    1000003 *** 182
    1000033 *** 197
    1000037 *** 183

We can observe that the time to test primes near 1,000,000 is nearly
2 times to that of primes near 1,000. However, because the selected
primes is too small (for today's computer), these results cannot clearly
demonstrate the logarithmic growth of this algorithm.