CSE 1729 – Introduction to Principles of Programming Due: February 18, 2019 Problem Set 3
Honor code. As a student in 1729, you have pledged to uphold the 1729 honor code. Specifically, you have pledged that any work you hand in for this assignment must represent your individual intellectual effort.
Remark: 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.
You can convert between exact and decimal numbers using the Scheme functions (exact->inexact n) and (inexact->exact n).
1. Define Hn = 1 + 1 + . . . + 1 ; these are referred to as the harmonic numbers. A remarkable fact 12n
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).
(a) Show how to use Scheme to compute Hn by writing a Scheme function named (harmonic n).
(b) Using your harmonic function, write a function (euler-approx n) that gives an estimate of Euler’s constant based on Hn. (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)))))
(and (> n 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.) We will use this function to develop a function (kth-prime k) which evaluates to the kth prime in the sequence 2, 3, 5, 7, . . ..
(a) The key to this problem is to break it down into smaller parts. First, write a function (next-prime-after n) which finds the smallest prime number that is greater than n. (next-prime-after 7) should evaluate to 11; (next-prime-after 10) would also evalu- ate to 11.
(b) Using the function (next-prime-after n), write the function (kth-prime-after n k) that evaluates to the kth prime that is greater than n. For example, (kth-prime-after 3 1) evaluates to 5, and (kth-prime-after 3 5) evaluates to 17.
(c) Finally, write a function (kth-prime k) that uses the above functions to returns the kth prime number. For example, (kth-prime 1) evaluates to 2, (kth-prime 5) evaluates to 11, and so forth. This is the easy part!
3. In lecture we presented code for sqrt-converge, which approximates a square root by starting with an interval that contains the square root, testing whether the midpoint of that interval is greater than or less than the actual square root, and then recursively calling itself on either the upper or lower half of the interval. In this problem you will generalize that code so it produces the nth root of a number for any positive integer n.
(a) As part of this, we will need to be able to raise a number to the nth power where n is a positive integer – to be used analogously to square in the lecture code. We could use the following function, (power base exp), that raises a number (base) to a power (exp):
But we will be using this a lot, so we want to be more efficient. Design a Scheme function fast-expt which calculates be for any integer e ≥ 0 by the rule:
(define (power base exp) (cond ((= exp 0) 1)
(else
(* base (power base (- exp 1))))))
e2e
b = (b)2 ifeiseven, 2e−1
b ∗ (b ) 2 if e is odd.
You may want to try the even? and odd? functions defined in Scheme. Notice that this is
1 ife=0,
not the rule used for fastexp in Lab.
(b) Once fast-expt is working, you can define your (nth-root-approx x n tol) function, which approximates the nth root of x, √n x. The approximation should be close enough so your approximation is within tol of x. Use the structure of sqrt-converge as a guide. Do not make fast-expt a local function of nth-root-approx, because it will be tested separately.
(c) InhisFundamentalAlgorithms,computerscientistDonaldKnuthasksthequestionwhether
√n n has a limit as n → ∞. Use your nth-root-approx function to write (nth-root-of-n-approx
n tol), which evaluates to an approximation (within tol of √n n). Test it on some n val- ues – does it seem to have a limit? Encode your answer in the (simple) Scheme function (nth-root-of-n-has-limit?) that evaluates to #t if √n n has a limit as n → ∞, #f otherwise.
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+ 1
φ
1+1 1+…
Define a recursive Scheme function named (golden n) which takes one parameter, n, and computes an approximation to the value of this continued fraction by expanding it to depth n. To be precise, define
φ0 = 1 ,
φ1 = 1 + 1 = 2 ,
1
φ2=1+ 1 =3,
1+1 2 1
φ3 =1+ …
1 =12,
1+13
1+1 1
or, more elegantly,
φ0 = 1 ,
φn = 1 + 1 for n > 1.
φ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:
√
φ= 1+ 1+ 1+ 1+···
Define a Scheme function named (golden-sqrt n) that takes one parameter, n, and com- putes the nth convergent of the golden ratio using the continued square root. (Use the Scheme function (sqrt x) which returns the square root of x.) As with the previous problem, the 0th convergent (that is, (golden-sqrt 0)) should be 1.
The next three questions require the use of a function that generates a random number. I have supplied Scheme code with this assignment in file r5rs-random.rkt, so you can conveniently copy and paste it into your problemSet3.rkt file. This code has a number of features that we have not yet seen in Scheme; use it as it is and trust that we will learn those features later. It includes a function random that produces a uniformly-distributed random value between 0.0 and 1.0; that is the probability that (random) is less than a value x (where x is between 0 and 1) is x; for example, the probability that (random) is less than .5 is .5, the probability that (random) is less that .7 is .7, and so forth. The value returned by random is always greater than 0.0 and less than 1.0. This function produces a sequence of pseudo-random numbers; when initialized with the same seed it will produce identical sequences.
Before you use (random) you need to initialize it by evaluating the function (init-random); if you copy and paste the code from r5rs-random.rkt into the top of your definitions file it will do so when you do a run. Every time you do this initialization the sequence of random numbers will start over from the same place; you only need to initialize once.
5. While the supplied function is fine for generating uniform random values between zero and one, sometimes we would like discrete values – for example, we would like to produce random integers over a range.
(a) WriteaSchemefunction(random-int k)thatreturnsanintegerintherange{1,2,…,k}; the probability of each integer being returned should be the same.
How do I do this? (random) returns a floating point number between 0 and 1; if I multiplied those values by k I would get floating point values between 0 and k. There are a couple of built-in functions that you could use to get discrete values: (ceiling v) takes a value v and returns the smallest whole value greater than or equal to v ; (floor v) takes a value v and returns the largest whole value less than or equal to v . ceiling and floor return decimal numbers (like 4.0 rather than 4); you should use the built-in function (inexact->exact d) to convert the result to an integer.
(b) Write a Scheme function (random-int-range a b) that returns an integer in the range {a, . . . , b}; the probability of each integer being returned should be the same. Your function should work for any integer values of a and b such that a ≤ b.
6. Testing whether a number is prime (as we did above) can be quite expensive for large numbers, as we might have to check a lot of possible divisors; the version above checks all the values from 2 to n − 1 if n is a prime number. In this problem, we will use a result from number theory and your random-int function to do a bit better.
Background: Fermat’s Little Theorem states: If n is a prime number and a is any positive integerlessthann,thenan iscongruenttoamodn,thatis,an modn=amodn,oran anda have the same remainder when divided by n. How can we use this? If we have a number n and a smaller number a, and an mod n ̸= a mod n, then we know that n is not prime. It happens to be the case that for most composite (non-prime) numbers, this test will fail for most values of a. The idea is that we will do this comparison on a few randomly-selected a values and get a decision that is correct nearly all of the time.
(a) Write a Scheme function (mod-test n a) which evaluates to #t if an mod n = a mod n. Noticethatsince0≤a
n k) that works as
• it calls (fermat-test n)
• if that returns #f, (fermat-prime?
• if (fermat-test n) returns #t, call fermat-prime? recursively
• if fermat-prime? has been called k times without returning #f, return #t
Basically, for n > 2 (fermat-test n) is called up to k times; if it returns #t every time, we say the number is prime. If n = 2, (fermat-prime? n k) should simply evaluate to #t.
Notice that this function will never say a prime number is not prime, as fermat-test will never be false for a prime number. It is possible that fermat-prime? can be true for a non-prime, but the likelihood of that gets smaller as k gets larger.
(d) An interesting thing about using fermat-prime? is that it works better on some numbers than others. For primes, (mod-test n a) is true for every a from 2 to n − 1; for most composite numbers (mod-test n a) is false for a large majority of a values, but there are exceptions.
n k) returns #f
Write a Scheme function (proportion-fermat-positives n) that determines the pro-
portion of a values for which (mod-test n a) is true, that is, the number of values from
{2, 3, . . . n−1} for which (mod-test n a) is true divided by n−2. (proportion-fermat-positives n) will be 1 for all primes, and vary for composites. Hint: 15 is pretty bad, 32 is very
good, if you want a quick test.
7. The game of Craps is a dice game in which the player rolls two dice. You will use a random number generator to simulate the playing of this game, and will estimate the odds of winning a “pass bet”.
The game works as follows. One person at a time is the “shooter”, the person rolling a pair of dice. A throw is the sum of two dice, each of which can range from 1 to 6. At the start of a turn, people bet money on a pass, that is, they bet that the shooter will be successful on this turn.
If the shooter’s first throw is a 7 or 11, he wins. If his first throw is a 2, 3, or 12, he loses. If neither of these is true, the value of that throw is the point for subsequent rolls. Now the shooter makes throws repeatedly until one of two things happens:
• If his throw has the same value as the point, he wins this turn • If he throws a 7, he loses this turn.
Your tasks are as follows:
(a) Write a Scheme function (throw-one-die) that evaluates to a random number over the range 1-6. Each of these values should be equally probable. Notice that (throw-one-die) has no parameters.
(b) Using (throw-one-die), write the Scheme function dice-throw, which returns the sum of two calls to (throw-one-die).
(c) Using (dice-throw) and the rules of the game, write the Scheme function (make-point point) which makes a throw and either returns #t, if the throw is equal to the point, #f if the throw is a 7, otherwise returns the result of the recursive call to make-point.
(d) Using (dice-throw) , (make-point point), and the rules of the game, write the Scheme function (make-pass). Make pass simulates one turn, and returns #t if the shooter wins, and #f if the shooter loses. This function should work like the game: it calls (dice-throw); if the throw was a 7 or 11 return #t, if the throw was a 2, 3, or 12 return #f, otherwise return (make-point point).
(e) Finally, write the Scheme function (win-odds n), which calls (make-pass) n times, and returns the proportion of games were won, that is, the number of times (make-pass) was #t divided by the number of times it was called (n).
Evaluate (win-odds n) for a range of values of n. What are the odds that a player wins a turn?
Once you have finished:
1. Save your work to a file using the appropriate filename, problemSet3.rkt. 2. Submit your solution file for grading via the MIMIR site.