# 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.

Updated: