[edit]
# Homework 3

## Template

## Autograder

## Exercise 1: Invariant for Fast Exponentiation

## Exercise 2: Golden Ratio (Optional)

## Exercise 3:

### Part 1

### Part 2

### Part 3

## Exercise 4:

## Exercise 5: Interchanging Base Cases

## Exercise 6: Invariant for Exponentiation

## Submit Your Homework!

Type the following command at the terminal to copy the template file to the current directory (note the period at the end):

```
cp ~cs61as/autograder/templates/hw3.rkt .
```

Or you can download the template here.

If you are working on the lab computers, the `grader`

command will run the autograder. If you are working on your own personal machine, you should download grader.rkt and the HW 3 tests.

Here is the `fast-expt`

procedure from earlier in this lesson:

```
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
```

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does `fast-expt`

.

(Hint: Using the observation that (*b*^{n/2})^{2} = (*b*^{2})^{n/2}, keep, along with the exponent *n* and the base *b*, an additional state variable *a*, and define the state transformation in such a way that the product *a b ^{n}* is unchanged from state to state. At the beginning of the process

Read the subsection on finding fixed points of functions in SICP, and do Exercise 1.35.

`cont-frac`

An infinite *continued* fraction is an expression of the form:

[mathjax]f=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\cdots}}}[/mathjax]

As an example, one can show that

[mathjax]\frac{1}{\phi}=\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}[/mathjax]

where [mathjaxinline]\phi=\frac{1+\sqrt{5}}{2}[/mathjaxinline] is the golden ratio.
One way to approximate an infinite continued fraction is to truncate the expansion after a
given number of terms. Such a truncation—a so-called *[mathjaxinline]k[/mathjaxinline]-term finite continued
fraction*—has the form:

[mathjax]\frac{N_1}{D_1+\frac{N_2}{\ddots+\frac{N_k}{D_k}}}[/mathjax]

Suppose that `n`

and `d`

are procedures of one argument
(the term index [mathjaxinline]i[/mathjaxinline]) that return the
[mathjaxinline]N[/mathjaxinline] and [mathjaxinline]D[/mathjaxinline] of
the [mathjaxinline]i[/mathjaxinline]-th term of the continued fraction.
Define a procedure `cont-frac`

such
that evaluating `(cont-frac n d k)`

computes the value of the [mathjaxinline]k[/mathjaxinline]-term
finite continued fraction. Check your procedure by approximating [mathjaxinline]\frac{1}{\phi}[/mathjaxinline]
using

```
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k)
```

for successive values of `k`

. How large must you make `k`

in order to get an approximation that is accurate to 4 decimal places?

If your `cont-frac`

procedure generates a recursive process, write one that generates an iterative process.
If it generates an iterative process, write one that generates a recursive process.

In 1737, Swiss mathematician Leonhard Euler showed that

[mathjax]
e - 2=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\cdots}}}
[/mathjax]

for the parameters

[mathjax]
\begin{cases}
N_i = 1\\
D_i = 1,2,1,1,4,1,1,6,1,1,8,\cdots
\end{cases}
[/mathjax]

where [mathjaxinline]e[/mathjaxinline] is the base of natural logarithms.
Write a program that uses your `cont-frac`

procedure to approximate [mathjaxinline]e[/mathjaxinline]
using Euler's expansion.

`next-perf`

A *perfect number* is defined as a number equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The second perfect number is 28, because 1+2+4+7+14=28. What is the third perfect number?

Write a procedure `(next-perf n)`

that tests consecutive integers starting with `n`

until a perfect number is found. Then you can evaluate `(next-perf 29)`

to solve the problem. Note that your procedure should be able to handle any non-negative integer input.

Hint: youâ€™ll need a `sum-of-factors`

subprocedure.

Note: If you run this program when the system is heavily loaded, it may take half an hour to compute the answer! Try tracing helper procedures to make sure your program is on track, or start by computing `(next-perf 1)`

and see if you get 6.

Here is the definition of `count-change`

program from earlier in this lesson:

`(define (count-change amount) (cc amount `(50 25 10 5 1)))`

`(define (cc amount kinds-of-coins) (cond [(= amount 0) 1] [(or (< amount 0) (empty? kinds-of-coins)) 0] [else (+ (cc amount (bf kinds-of-coins)) (cc (- amount (first kinds-of-coins)) kinds-of-coins))] ))`

Explain the effect of interchanging the order in which the base cases in the `cc`

procedure are checked.

That is, describe completely the set of arguments for which the original `cc`

procedure would return a different value or behave differently from a `cc`

procedure coded as given below, and explain how the returned values would differ.

```
(define (cc amount kinds-of-coins)
(cond
[(or (< amount 0) (empty? kinds-of-coins)) 0]
[(= amount 0) 1]
[else ... ] ) ) ; as in the original version
```

Here is the iterative exponentiation procedure from earlier in this lesson:

```
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
```

Give an algebraic formula relating the values of the parameters `b`

, `n`

, `counter`

, and `product`

of the iterative exponentiation procedure defined above.

(The kind of answer we're looking for is "the sum of `b`

, `n`

, and `counter`

times `product`

is always equal to 37.")

For instructions, see this guide. It covers basic terminal commands and assignment submission.

If you have any trouble submitting, do not hesitate to ask a TA!

3 - Recursion, Iteration, Efficiency