% Document Type: LaTeX
% Master File: ps1-intro.tex
% this has been revised by GJS (14-jan) and LDB (16-jan, 27-jan)
\input 6001mac
\def\fbox#1{%
\vtop{\vbox{\hrule%
\hbox{\vrule\kern3pt%
\vtop{\vbox{\kern3pt#1}\kern3pt}%
\kern3pt\vrule}}%
\hrule}}
\begin{document}
\psetheader{Spring Semester, 1992-93}{Problem Set 2}
\medskip
\begin{flushleft}
Issued: February 9, 1992 \\
\smallskip
Tutorial preparation for: Week of February 15 \\
\smallskip
Written solutions are due in Recitation:
\begin{itemize}
\item Even Numbered Recitation Sections: Wednesday February 17;
\item Odd Numbered Recitation Sections: Friday, February 19.
\end{itemize}
\smallskip
Reading:
\begin{tightlist}
\item Text: Complete Chapter 1.
\end{tightlist}
\end{flushleft}
\section{1. Tutorial Exercises}
\paragraph{Exercise 2.1}
Do exercise 1.23 of the text. You should make use of the
{\tt sum} procedure defined on p. 47 of the notes.
\paragraph{Exercise 2.2}
Do exercise 1.24 of the text.
\paragraph{Exercise 2.3}
Determine the orders of growth for the {\tt my-sine}
and {\tt recurrent-sine} procedures in Problem Set 1.
Consider both the growth
of space and number of operations and their dependence on the
size of the argument and the value of the global variable {\tt epsilon},
using the number of
applications of the {\tt my-sine} and {\tt recurrent-sine}
procedures to measure the number of operations.
How would the orders of growth for the {\tt my-sine} procedure
be changed if it had been defined as
\beginlisp
(define (my-sine x)
(if (small-enuf? x)
x
(* (my-sine (/ x 3))
(- 3
(* 4 (my-sine (/ x 3))
(my-sine (/ x 3)))))))
\endlisp
\paragraph{ Exercise 2.4 }
Procedure {\tt repeated} is defined as
\beginlisp
(define (repeated p n)
(cond ((= n 0) (lambda (x) x))
((= n 1) p)
(else (lambda (x) (p ((repeated p (-1+ n)) x))))))
\endlisp
Determine the values of the expressions
\beginlisp
((repeated square 2) 5)
\endlisp
and
\beginlisp
((repeated square 5) 2).
\endlisp
In tutorial you may be asked how the interpreter evaluates expressions
similar to these.
\section{2. Continued Fractions}
Continued fractions play an important role in number theory and in
approximation theory. In this programming
assignment, you will write some short procedures that evaluate
continued fractions. There is no predefined code for you to load.
An infinite continued fraction is an expression of the form
\begin{displaymath}
f={{N_1} \over
{\displaystyle D_1 + {{\strut N_2} \over
{\displaystyle D_2 + \ddots }}}}
\end{displaymath}
One way to approximate an irrational number is to expand as a
continued fraction, and truncate the expansion after a sufficient
number of terms. Such a truncation---a so-called {\em $k$-term finite
continued fraction}---has the form
\begin{displaymath}
{{N_1} \over {\displaystyle D_1+
{\strut {N_2} \over {\displaystyle \ddots +
{\strut {N_K} \over {\displaystyle D_K+0}}}}}}
\end{displaymath}
For example, if the $N_i$ and the $D_i$ are all 1, it is not
hard to show that the infinite continued fraction expansion
\begin{displaymath}
{1 \over {\displaystyle 1 +
{\strut 1 \over {\displaystyle 1 +\ddots } }}}
\end{displaymath}
converges to $1/\phi\approx .618$ where $\phi$ is the {\em golden ratio}
\begin{displaymath}
\frac{1+ \sqrt{5}}{2}
\end{displaymath}
The first few finite continued fraction approximations (also called
{\em convergents}) are:
\begin{displaymath}
1, \frac{1}{2}=.5, \frac{2}{3}\approx .667, \frac{3}{5}=.6,
\frac{5}{8}=.625, \cdots
\end{displaymath}
\paragraph{Pre-Lab Exercise 2.1}
Suppose that {\tt n} and {\tt d} are procedures
of one argument (the term index) that return the
$n_i$ and $d_i$ of the terms of the continued fraction.
Define procedures {\tt cont-frac-r} and {\tt
cont-frac-i} such that evaluating {\tt (cont-frac-r n d k)} and {\tt
(cont-frac-i n d k)} each compute the value of the $k$-term finite
continued fraction. The process that results from applying {\tt
cont-frac-r} should be recursive, and the process that results from
applying {\tt cont-frac-i} should be iterative. Check your procedures
by approximating $1/\phi$ using
\beginlisp
(cont-frac (lambda (i) 1)
(lambda (i) 1)
k)
\endlisp
for successive values of {\tt k}, where {\tt cont-frac} is {\tt
cont-frac-r} or {\tt cont-frac-i}. How large must you make {\tt k}
in order to get an approximation that is accurate to 4 decimal places?
Turn in a listing of your procedures.
\paragraph{Lab Exercise 2.2}
One of the first formulas for $\pi$ was given around 1658 by the
English mathematician Lord Brouncker:
\begin{displaymath}
4/\pi -1 = 1/(2 + 9/(2 + 25/ (2 + 49/ (2 + 81 /(2 + \cdots
\end{displaymath}
This leads to the following procedure for approximating $\pi$:
\beginlisp
(define (estimate-pi k)
(/ 4 (+ (brouncker k) 1)))
\endlisp
\beginlisp
(define (square x) (* x x))
\null
(define (brouncker k)
(cont-frac (lambda (i) (square (- (* 2 i) 1)))
(lambda (i) 2)
k))
\endlisp
where {\tt cont-frac} is one of your procedures {\tt cont-frac-r} or
{\tt cont-frac-i}. Use this method to generate approximations to $\pi$.
About how large must you take $k$ in order to get 2 decimal places
accuracy? (Don't try for more places unless you are very patient.)
\subsection{Computing inverse tangents}
Continued fractions are frequently encountered when approximating
functions. In this case, the $N_i$ and $D_i$ can themselves be
constants or functions of one or more variables. For example, a
continued fraction representation of the inverse tangent function
was published in 1770 by the German mathematician J.H. Lambert:
\begin{displaymath}
{\tan^{-1}x} ={x \over
{\displaystyle 1+{\strut {\left( {1x} \right)^2} \over
{\displaystyle 3+{\strut {\left( {2x} \right)^2} \over
{\displaystyle 5+{\strut {\left( {3x} \right)^2} \over {7+\ddots }}}}}}}}
\end{displaymath}
\paragraph{Pre-Lab Exercise 2.3}
Define a procedure {\tt (atan-cf k x)} that computes an approximation
to the inverse tangent function based on a $k$-term continued fraction
representation of $\tan^{-1} x$ given above. Provided you use the
correct arguments, it should be possible to
define this procedure directly in terms of the {\tt cont-frac}
procedure you have already defined.
\paragraph{Lab Exercise 2.4}
Verify that your
procedure works (and check its accuracy) by using it to compute the
tangent of a number of arguments, such as $0$,
$1$, $3$, $10$, $30$, $100$.
Compare your results with those computed using
Scheme's {\tt atan} procedure\footnote{Evaluating {\tt (atan x)}
returns the same value as {\tt (atan x 1)}, an angle in the range
$(-\pi/2, +\pi/2)$.}.
How many terms are required to get
reasonable accuracy? Turn in your procedure definition
together with some sample results.
The idea of a continued fraction can be generalized to include
arbitrary nested expressions such as (1) and (2) below:
\begin{equation}
%MathType!ZZhx46!633xZh9VgeZpaeVeH9Kppzqiq9taFeGa2-Y8WaXhsyprZBeecuFmWh
%bif9Y+se2t+8KbHa1pc8racy-lZddeFiH9enVrqiq9YaFeGu0lRu03
%Nu0l7lryp5ZtgeVeH92cFeGa2-Y8WaXhsyprZBeeFiH9RbFeGu0lRa
%1paaaaaaa8!2AB6!
\left( {N_1/\left( {D_1+N_2/\left( {D_2+\cdots +N_k/\left( {D_k+0}
\right)} \right)} \right)} \right)
\end{equation}
\begin{equation}
%MathType!ZZhx46!633xZh9VgeZpaeVeH9Kppzqiq9taFeGu0VYhsyprZBeecuFmWhbif9
%ln-aq8se2t+8KbHa1pc8rasr-kFiH9enVrqiq9YaFeGu0VKu03Nu0V
%08daXlryp5ZtgeVeH92cFeGu0VYhsyprZBeeFiH9RbFeGu0VKa1pba
%aaaap!2B00!
\left( {N_1+D_1\times \left( {N_2+D_2\times \cdots \times \left(
{N_k+D_k\times 1} \right)} \right)} \right)
\end{equation}
or in general
\begin{displaymath}
\left( T_1 {\cal O}_1 \left( T_2 {\cal O}_2 \cdots
\left( T_k {\cal O}_k R \right) \right) \right)
\end{displaymath}
where the $T_i$ are the terms of the expression,
the ${\cal O}_i$ are the arithmetic operators, and $R$ is the
residual term (perhaps representing the effects of
terms beyond the $k$th in an approximation). For example,
in (2) the ${\cal O}_i$ are alternately the addition and the
multiplication operators, and $R=1$.
\paragraph{Pre-Lab Exercise 2.5}
Define a procedure {\tt nested-acc} such that evaluating {\tt
(nested-acc op r term k)} computes the value of a nested expression.
Argument {\tt op} is a procedure of one argument, that when applied to
the term index $i$ returns the $i$th arithmetic operation ${\cal O}_i$
(which is a procedure of two arguments). The {\tt r} argument
represents the effect of the $R$ term. Turn in a listing of your
procedure.
How would you use your {\tt nested-acc} procedure to
compute a $k$-term approximation to the function
\begin{displaymath}
%MathType!ZZhx46!633xZh9VgeZtbecu-esrVSZtbecu-esrVSZtbecu-esrVSsrFFWhba
%Fea8raaa!0C5C!
f(x)=\sqrt {x+\sqrt {x+\sqrt {x+\cdots }}}
\end{displaymath}
\paragraph{Lab Exercise 2.6}
Verify that your {\tt nested-acc} procedure works properly
by computing an approximation to $f(1)$, whose value is
the golden ratio. How large must you make {\tt k}
in order to get an approximation that is accurate to 4 decimal places?
Turn in a listing of your procedures.
\paragraph{Lab Exercise 2.7}
Verify that your {\tt nested-acc} procedure works
properly by using it to compute the value of the Taylor series for the
sine function discussed in Problem Set 1.
In certain continued fractions all $N_i$ and $D_i$ terms are equal
and it is convenient to regard the fraction as
being ``built-up'' from a base by a repetitive operation. For
example, given the base function $B$ and the augmentors
$N$ and $D$, one can build $N/(D+B)$. This can be computed in a
straightforward fashion by the procedure {\tt build}
\beginlisp
(define (build n d b)
(/ n (+ d b)))
\endlisp
The value of the expression that is represented by the two-term
continued fraction
\begin{displaymath}
%MathType!ZZhx46!633xZh9VgeZtdeVeH9KdXlryprsrVSZtdeVeH9KdXlryprsrVSVeH9
%Kaaaa8!1036!
{N \over {D+{N \over {D+B}}}}
\end{displaymath}
can then be computed by evaluating {\tt (build n d (build n d b))}.
When further composition is of interest, it is possible to use the
{\tt repeated} procedure defined above.
\paragraph{ Pre-Lab Exercise 2.8 }
Write a procedure {\tt repeated-build} of four arguments {\tt k},
{\tt n}, {\tt d}, and {\tt b}, which returns a result
that is equivalent to applying the {\tt build} procedure $k$ times. In
particular {\tt (repeated-build 2 n d b)} should return the same result
as {\tt (build n d (build n d b))}. Your implementation of {\tt
repeated-build} should make use of the {\tt repeated} procedure given above
(in a non-trivial way).
\paragraph{ Lab Exercise 2.9 }
Verify that your {\tt repeated-build} procedure works properly by evaluating
the continued fraction for the reciprocal of the golden ratio:
\begin{displaymath}
{1 \over {\displaystyle 1 +
{\strut 1 \over {\displaystyle 1 + \ddots } }}}
\end{displaymath}
converges to $1/\phi\approx .618$ where $\phi$ is the {\em golden ratio}
Now consider the problem of computing the rational functions
$r_1(x)=(1+0x)/(1+x)$, $r_2(x)=(1+x)/(2+x)$, $r_3(x)=(2+x)/(3+2x)$,
\begin{displaymath}
%MathType!ZZhx46!633xZh9VgeVeH9Nmpzq8se2Bl8raZddeFiH94bGu03Z8dbXhsyFyZB
%eeFiH9RbFeGu0l7lryVfZtgeVeH92kf9slq9taFeWhsypEq8He2h28
%gbXhsy-Asr-kcuFmWhbif9Y+se2BX8KbXlryVTWhb8He2JhasrFpZp
%eecuFmqiq9Xif9R8He2l38gbXhsy-AsrFlcuFmWhbm-aq8se2Fiaaa
%Wd!3C40!
r_k\left( x \right)={{a_k+a_{k-1}x} \over {a_{k+1}+a_kx}}={1 \over
{1+r_{k-1}\left( x \right)}}
\end{displaymath}
where $a_k$ is the $k$-th Fibonacci number ($a_0=0$).
\paragraph{ Lab Exercise 2.10 }
Making use of your {\tt repeated-build} procedure, define a procedure
{\tt r} of one argument {\tt k} that evaluates to a procedure of
one argument {\tt x} that computes $r_k(x)$. For example,
evaluating {\tt ((r 2) 0)} should return $0.5$.
\subsection{Optional Problem}
One difficulty with using continued fractions to evaluate functions
is that there is generally no way to determine in advance how many
terms of an infinite continued fraction are required to achieve a
specified degree of accuracy. The result obtained by computing the
value of a continued fraction by working backwards from the $k$-th to
the first term cannot generally be used in the computation of the
$k+1$ term continued fraction.
Remarkably, there is a general technique for computing the value of a
continued fraction that overcomes this problem. This result is based
on the recurrence formulas
\begin{equation}
A_{-1}=1;B_{-1}=0;A_0=0;B_0=1
\end{equation}
\begin{equation}
%MathType!ZZhx46!633xZh9VgeVeH9umpzq8se2Bk8rasrFpFiH9enVrq8He2Rg8raVeH9
%umpzq8se2BQu0lTa1pb8rasr-kFiH9onVrq8He2Rg8raVeH9umpzq8
%se2BQu0lTa1pc8raaa!212C!
A_j=D_jA_{j-1}+N_jA_{j-2}
\end{equation}
\begin{equation}
%MathType!ZZhx46!633xZh9VgeVeH9Kmpzq8se2Bk8rasrFpFiH9enVrq8He2Rg8raVeH9
%Kmpzq8se2BQu0lTa1pb8rasr-kFiH9onVrq8He2Rg8raVeH9Kmpzq8
%se2BQu0lTa1pc8raaa!212F!
B_j=D_jB_{j-1}+N_jB_{j-2}.
\end{equation}
It is easy to show that the $k$-term continued fraction can be computed as
\begin{equation}
%MathType!ZZhx46!633xZh9VgeVeH9Mnpzq8se2Bl8rasrFpZpeeFiH9bnVrq8He2Vg8ra
%q8se2tY8KbXlryVTWhbaaa!1500!
f_k={{A_k} \over {B_k}}.
\end{equation}
By determining whether $f_j$ is close enough to $f_{j-1}$, it is easy
to determine whether to include more terms in the approximation.
Define a procedure that computes the value of a continued fraction
using this algorithm. The process that evolves when the procedure is
applied should be iterative. Test that your procedure works by
computing the tangent of various angles. Use the tracing feature of
SCHEME to determine how many terms are evaluated.
\vspace{10ex}
Turn in this sheet with your answers to the questions in the problem set.
\vspace{6ex}
How much time did you spend on this homework assignment? Report separately
time spent before going to lab and time spent in the 6.001 lab.
\vspace{6ex}
If you cooperated with other students working this problem set
please indicate their names in the space below. As you should know,
as long as the guidelines described in the
{\em 6.001 Policy on Cooperation}\ handout are followed,
such cooperation is allowed and encouraged.
\end{document}