# SICP Solutions: Sections 1.2.5 and 1.2.6

### Section 1.2.5 - Greatest Common Divisors

#### Exercise 1.20

The difference between applicative and normal order is that applicative first
evaluates the arguments and then applies the procedure. In contrast, normal
order first expands the procedure and then reduces it. Also note that `if`

is a
special form, where which (and whether) procedure is evaluated depends on the
predicate.

Let’s first see the applicative order:

In the normal order, we first expand and then apply only as needed. So:

So in summary, the normal order will need:
\(1 + 2 + 4 + 7 + 4 = 18\) calls to `remainder`

.

### Section 1.2.6 - Example: Testing for Primality

#### Exercise 1.21

So while \(199\) and \(1999\) are primes, \(19999\) is not.

#### Exercise 1.22

\(\sqrt{10} = 3.17\). This means that we expect time to roughly triple between orders of magnitude. Our results are:

The results roughly confirm our calculations. We wouldn’t expect exact results since the actual timing depends on a lot of things.

#### Exercise 1.23

Essentially the steps taken by the algorithm will now be limited by $\sqrt{n}/2$. This means that $\sqrt{n}$ will still dominate the algorithm, but given a large-enough input the time will be roughly halved.

#### Exercise 1.24

We would expect the time to test primes near $1,000,000$ to be roughly the triple of the time to test primes near $1,000$. We do not obseve even that kind of change, probably due to fast hardware, but we do observe that the runtime grows very slowly.

#### Exercise 1.25

While conceptually Alyssa is correct, in practice the call to `fast-expt`

will
result in dealing with big numbers, and trying to find their `remainder`

. Our
`expmod`

method will always find the remainder of small numbers, multiply them
together, find their remainder, etc. See footnote 46. Bear in mind also that
primality checks are usually done for very large numbers.

The results are pretty grave in practice:

#### Exercise 1.26

By rewriting the `expmod`

procedure to use explicit multiplication, Louis has
changed it into a tree recursive process from a linear one. This means that in
each steps two subtrees will be created, and the amount of calls grow
exponentially. So \(2^{\log n} = n\).

#### Exercise 1.27

We create a procedure `congruent?`

as such:

Calling the procedure for the Carmichael numbers of footnote 47 (561, 1105,
1729, 2465, 2821 and 6601) we always get `#t`

. The `fast-prime?`

procedure would
be fooled. However, we can use the `prime?`

procedure to confirm that these
numbers are not primes.

#### Exercise 1.28

First we create the function that performs the check and short-circuits the computation:

We want to use the above before squaring the result of each iteration. Since we
cannot store variables yet, what we can do is wrap the `expmod`

call to itself
inside a `miller-rabin-check`

call. `miller-rabin-check`

will get the result of
the previous iteration as input, and check whether it is a non-trivial square
root of 1. If it is, it will return 0, essentially short-circuting the result.
If it is not, it will return the result, thus letting `expmod`

continue as
usual.

Finally, we can run the check for half the size of the input to make sure we produce the correct answer:

We can use both the prime numbers we found and the Carmichael numbers to confirm that our new procedure always produces the correct result and is not fooled.