Description
Remark 1. The Racket interpreter can maintain two different representations of numeric quantities: fractions and
decimal representations. While fractions always represent exact numeric quantities, decimal expansions maintain a
finite number of digits to the right of the decimal point. The Racket interpreter will attempt to infer, when dealing with
numbers, whether to maintain them as fractions or as decimal expansions. For example
> (/ 1 2)
1/2
> (/ 1 2.0)
0.5
> (+ (/ 1 2) (/ 1 3) (/ 1 6))
1
> (+ (/ 1 2) (/ 1 3.0))
0.8333333333333333
>
In general, the interpreter will maintain exact expressions for numeric quantities “as long as possible,” expressing them
as fractions. You can instruct the interpreter that a number is to be treated as a decimal by including a decimal point:
thus 1 is treated as an exact numeric quantity, whereas 1.0 is treated as a decimal expansion. The interpreter knows
how to convert fractions to decimals (you can configure the number of digits of accuracy you wish), but will never
convert decimals back to fractions (or integers). (So you know, this process is called type-casting.)
Arithmetic expressions like (+ 1 1.0) pose a problem because the two arguments are of different “types.” In
this case, the interpreter will transform the exact argument (1) into a decimal value, and then proceed as though all
arguments were decimals (returning a decimal result). Other arithmetic operations are treated similarly.
1. Define Hn =
1
1 +
1
2 + . . . +
1
n
; these are referred to as the harmonic numbers. A remarkable fact about these
numbers is that as n increases, they turn out to be very close to ln n. (ln n is the natural logarithm of n.) In
particular, as n increases the difference |Hn − ln n| converges to a constant (Euler’s constant). Show how to
use SCHEME to compute Hn and, using this, give an estimate of Euler’s constant. (You may wish to use the
SCHEME function (log x) which returns the natural logarithm of x.) So you know you are in the ballpark,
Euler’s constant is a little over a half.
2. A integer n > 1 is prime if its only positive divisors are 1 and n. (The convention is not to call 1 prime.) The
following scheme procedure determines if a number is prime.
( define ( prime ? n )
( define ( divisor ? k ) (= 0 ( modulo n k )))
( define ( divisors-upto k )
( and ( > k 1)
( or ( divisor ? k ) ( divisors-upto (- k 1)))))
( not ( divisors-upto (- n 1))))
(So, it returns #t for prime numbers like 2, 3, 5, 7, and 11 and #f for composite (that is, non-prime) numbers
like 4, 6, 8, and 9.) Using this procedure, write a function count-primes so that (count-primes t)
returns the number of prime numbers between 1 and t.
3. The Lucas numbers are a sequence of integers, named after Édouard Lucas, which are closely related to the
1
Fibonacci sequence. In fact, they are defined in very much the same way:
Ln =
2 if n = 0,
1 if n = 1,
Ln−1 + Ln−2
if n > 1.
(a) Using the recursive description above, define a SCHEME function Lucas which takes one parameter, n,
and computes the n
th Lucas number Ln
.
(b) The small change in the “base” case when n = 0 seems to make a big difference: compare the first few
Lucas numbers with the first few Fibonacci numbers. As you can see, the Lucas numbers are larger,
which makes sense, and—in fact—the difference between the nth Lucas number and the nth Fibonacci
number grows as a function of n.
Consider, however, the ratio of two adjacent Lucas numbers; specifically, define
`n =
Ln
Ln−1
.
Write a SCHEME function Lucas-ratio that computes `n
(given n as a parameter). Compute a few
ratios like `20, `21, `22, . . . ; what do you notice? (It might be helpful to convince SCHEME to print out
the numbers as regular decimal expansions. One way to do that is to add 0.0 to the numbers.)
Now define
fn =
Fn
Fn−1
where Fn are the Fibonacci numbers. As above, write a SCHEME function Fibonacci-ratio to
compute fn and use it to compute a few ratios like f20, f21, f22, . . . ; what do you notice?
(c) Computing with a promise. Ask your SCHEME interpreter to compute L30, then L35, then L40. What
would you suspect to happen if you asked it to compute L50?
Consider the following SCHEME code for a function of four parameters called fast-Lucas-help. The
function call
(fast-Lucas-help n k lucas-a lucas-b)
is supposed to return the nth Lucas number under the promise that it is provided with any pair of previous
Lucas numbers. Specifically, if it is given a number k ≤ n and the two Lucas number Lk and Lk−1
(in
the parameters lucas-a and lucas-b), it will compute Ln
. The idea is this: If it was given Ln and
Ln−1
(so that k = n), then it simply returns Ln
, which is what is was supposed to compute. Otherwise
assume k < n, in which case it knows Lk and Lk−1 and wishes to make some “progress” towards the
previous case; to do that, it calls fast-Lucas-help, but provides Lk+1 and Lk
(which it can compute
easily from Lk and Lk−1
). The code itself:
( define ( fast-Lucas-help n k luc-a luc-b )
( if (= n k )
luc-a
( fast-Lucas-help n (+ k 1) (+ luc-a luc-b ) luc-a )))
With this, you can define the function fast-Lucas as follows:
( define ( fast-Lucas n ) ( fast-Lucas-help n 1 1 2))
(After all, L0 = 2 and L1 = 1.)
Enter this code into your SCHEME interpreter. First check that fast-Lucas agrees with your previous
recursive implementation (Lucas) of the Lucas numbers (on, say, n = 3,4,5,6). Now evaluate
(fast-Lucas 50) or (fast-Lucas 50000).
2
There seems to be something qualitatively different between these two implementations. To explain it,
consider a call to (Lucas k); how many total recursive calls does this generate to the function Lucas
for k = 3, 4, 5, 6? Now consider the call to (fast-Lucas-help k 1 1 2); how many recursive calls
does this generate to fast-Lucas-help for k = 3,4,5,6? Specifically, populate the following table
(values for k = 1, 2 have been filled-in):
Recursive calls made by
(Lucas k)
Recursive calls made by
(fast-Lucas-help k 1 1 2)
k = 1 0 0
k = 2 2 1
k = 3
k = 4
k = 5
k = 6
4. In mathematics and other fields, two quantities a > b are said to have the golden ratio if
a + b
a
=
a
b
.
For example, the heights of alternate floors of Notre Dame cathedral are in this proportion, as are the
spacings of the turrets; the side-lengths of the rectangular area of the Parthenon have this ratio.
Mathematically, it is easy to check that if a and b have this relationship then the ratio φ = a/b is the unique
positive root of the equation φ + 1 = φ
2
, which is approximately 1.618.
(a) An alternate form for the golden ratio is given by φ = 1 +
1
φ
. This formula can be expanded recursively
to the continued fraction:
φ = 1 +
1
1 +
1
1+
.
.
.
Define a recursive SCHEME function which takes one parameter, n, and computes an approximation to
the value of this repeated fraction by expanding it to depth n. To be precise, define
Φ1 = 1 +
1
1
= 2 ,
Φ2 = 1 +
1
1 +
1
1
=
3
2
,
Φ3 = 1 +
1
1 +
1
1+
1
1
= 1
2
3
,
. . .
or, more elegantly,
Φ1 = 2 ,
Φn = 1 +
1
Φn−1
for n > 1.
Your function, given n, should return Φn
.
(b) Another form of the golden ratio is given by the formula φ
2 = 1 + φ. This gives a recursive formula for
a continued square root:
φ =
s
1 +
r
1 +
q
1 +
p
1 + ···
3
Define a SCHEME function that takes one parameter, n, and computes the n
th convergent of the golden
ratio using the continued square root. (Use the SCHEME function (sqrt x) which returns the square
root of x.)
5. Consider the task of approximating the number π. There are many ways to proceed; in this problem you
will explore one method based on a process known as monte-carlo sampling.
We begin by inscribing a circle (of some radius r) inside a square, as shown in the picture.
r
Then, compute the ratio of the area of the circle to the area of the square. This ratio ρ is
ρ =
πr
2
(2r)
2
=
π
4
.
Of course, if we could compute ρ exactly that would be great, because π is exactly 4 · ρ.
Our strategy will be to approximate ρ by throwing darts randomly into the square. Consider a dart thrown
into the square by selecting each of its x and y coordinates by drawing randomly (and uniformly) from the
interval [−r,r]. It follows that the probability that the dart lies in the circle is precisely ρ. If we throw n
random darts into the square acording to this rule, we would expect that the fraction that fall in the circle is
close to ρ:
ρ ≈
number of darts in the circle
n
.
The algorithm you are required to write computes an estimate of π via this method. It takes as input an
integer n indicating how many darts should be thrown. It then proceeds by throwing the darts uniformly at
random at a square of side 2 centered at the origin (so both the x and y coordinates of the spot where the
dart lands are random numbers between -1 and 1). The algorithm must determine, for each dart, where it
lands (inside or outside the circle?) and tally the darts that fall inside. The estimate for ρ and therefore π
directly follow.
Of course, you will need a mechanism for generating random numbers: The SCHEME function called random
produces a “random” floating point value between 0 and 1. To obtain a random number in the range
[−1,1], for example, you can evaluate the SCHEME expression (- (* 2 (random)) 1). (Why is this
syntax correct?)
As for structuring your code, I suggest that you first write a function
( define ( one-sample ) …)
which throws one sample into the square and returns a 1 if the sample fell in the circle, and a 0 otherwise.
One easy way to structure this function is to use a let statement to first bind two variables x and y to two
random values. Note that if you have the x and y coordinates of a vector in the plane, it is easy to tell if it
fell in the circle: this happens exactly when x
2 + y
2 ≤ 1. Then, write a function
( define ( pi-samples k ) …)
4
which throws k (random) samples into the unit square and returns the number of them that fell into the
circle. Now what?
6. Consider the problem of defining a function interval-sum so that (interval-sum m n) returns the
sum of all the integers between m and n. (So, for example (interval-sum 10 12) should return the
value 33 = 10 + 11 + 12.) One strategy is
( define ( interval-sum m n )
( if (= m n )
m
(+ n ( interval-sum m (- n 1)))))
and another solution, which recurses the “other direction” is
( define ( interval-sum m n )
( if (= m n )
m
(+ m ( interval-sum (+ m 1) n ))))
These both work. It seems like one should be able to combine these to produce another version:
( define ( interval-sum m n )
( if (= m n )
m
(+ m
( interval-sum (+ m 1) (- n 1))
n )))
But this only works for certain pairs of input numbers. What’s going on?
5
