CSE 1729 – Introduction to Principles of Programming September 25, 2016 Problem Set 3
Note: this week’s homework requires the use of the random function, which is defined in the Racket dialect of SCHEME, but not in R5RS. For this week’s homework, therefore, you will need to choose Racket as your language. You can do this using Change language in Dr. Racket.
Other than random, all the functions you use should be in R5RS.
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. Recall from high-school trigonometry the cos function: If T is a right triangle whose hypotenuese has length 1 and interior angles x and ⇡/2 x , cos( x ) denotes the length of the edge adjacent to the angle x (here x is measured in radians). You won’t need any fancy trigonometry to solve this problem.
1
sin x cos x
It is a remarkable fact that for all real x,
cosx=1 2! + 4! 6! +···
1
angle x
Figure 1: A right triangle.
x2 x4 x6
Write a SCHEME function new-cos so that (new-cos x n) returns the sum of the first (n + 1) terms of this power series evaluated at x . Specifically, (new-cos x 3), should return
x2 x4 x6 1 2! + 4! 6!
and, in general, (new-cos x n) should return Xn
k=0
( 1)k
x 2 k (2k)!
.
You may use the built-in function (expt x k), which returns xk. It might make sense, also, to define factorial as a separate function for use inside your new-cos function. The value 2k is used multiple times in the definition of the kth term of this sum. Use a let statement to avoid computing this quantity more than once.1
2. Define H = 1 + 1 + . . . + 1 ; these are referred to as the harmonic numbers. A remarkable fact about these n12 n
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). Define a SCHEME function (harmonic n) that computes Hn, and use it in a second function that you define, (euler-approx n) that approximates Euler’s constant from Hn. Do not define (harmonic n) as a local function within
(euler-approx n).
3. In the text and in lecture, we have worked with the Fibonacci numbers, defined as follows:
8<0 Fibn =:1
Fibn 1 + Fibn 2
In section 1.2.2, we have two SCHEME implementations of Fib, one that is tree recursive (we will call that one
fib) and one that is iterative (we will call that one fib-i). Both should calculate the same value.
(a) Computing with a promise. Using the tree-recursive version of fib, ask your SCHEME interpreter to compute Fib30, then Fib35, then Fib40. What do you expect would happen if you asked it to compute Fib50? Consider the alternative fib-i (the one that uses fib-iter). What happens when you use it to compute Fib50? How about Fib500?
There seems to be something qualitatively different between these two implementations. To explain it, consider a call to (fib k); how many total recursive calls does this generate to the function fib for k = 3, 4, 5, 6, 7, 8? Now consider the call to (fib-i k); how many recursive calls does this generate to fib-iter for k = 3, 4, 5, 6, 7, 8? Specifically, populate the following table (values for k = 1, 2 have been filled-in):
if n = 0, ifn=1, if n > 1.
Recursive calls made by
(fib k)
Recursive calls made by
(fib-iter k 1 0)
k=1
0
1
k=2
2
2
k=3
k=4
k=5
k=6
k=7
k=8
1This is of dubious value here as 2k is quite easy to calculate, but it practices your let skills. 2
(b) Fibonacci numbers monotonically increase with n (that is, they keep getting larger as n increases). Consider, however, the ratio of two adjacent Fibonacci numbers; specifically, define
fn= Fibn . Fibn 1
Write a SCHEME function fib-ratio that computes fn (given n as a parameter). Compute a few ratios like f20, f21, f22, …; 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, or use a decimal number (something.0) as argument to fib-ratio.
4. In mathematics and other fields, two quantities a > b are said to have the golden ratio if
a+b=a. ab
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+…
Define a recursive SCHEME function (golden n) which computes an approximation to the value of this
repeated fraction by expanding it to depth n. To be precise, define 1 = 1 + 1 = 2 ,
or, more elegantly,
for n > 1.
Your function applied to n, that is, (golden n), should evaluate to n.
(b) Another way to get the golden ratio is to approximate it as we did with square root in lecture. We can do so as follows: write a function (golden-approx a b n) that provides an approximation to after cutting the interval in half n times. For this to work, we need to guarantee that it is always true that a < b – that is, is in the interval (a, b) – and each recursive call is made with an interval half the size: (a, average(a, b)) if average(a, b)) > , and (average(a, b), b) if average(a, b)) .
How can I tell if a number is greater than or less than ? If x = , then x2 = x + 1. We can determine whether a non-negative x is greater than or less than by comparing x 2 and x + 1 (look at a few cases and see how). You can start golden-approx with any 2 non-negative values of a and b such that is between them (1 and 2, e.g., or 0 and 4).
Since these two functions both calculate you can use them to check each other. Which function works better?
3
=1+ 1 1+1
1
2=1+ 1 =3,
1+1 2 1
3 =1+ …
1 =12, 1+11 3
1+1
1 =2, n = 1 +
1 n 1
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.
Then, compute the ratio of the area of the circle to the area of the square. This ratio ⇢ is ⇡r2 ⇡
⇢ = (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.
You should write a SCHEME function (pi-approx n) that gives you 4 times the proportion of n random darts that end up inside the circle. A reasonable approach would be to have a helper function that approximates ⇢ and have pi-approx use that.
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?)
4
r