Page 1 of 1

### Homework for tomorrow!

Posted: Sun May 27, 2018 4:28 am
Dear all,

There is an important question that I don't understand in my problem set due tomorrow, and any help would be much appreciated if anyone is willing to help/take the challenge!!! (or in priority questions a, b, c)

The question is as follows:

Reconsider the Monte Carlo approximation of the mathematical constant π. One approach we discussed involves drawing random points from a unit square and testing whether these points lie within the unit circle. The predicate is:
(define (circle-test?)
(<= (+ (expt (rand) 2) (expt (rand) 2)) 1))

(a) (10 points) We aim to replace rand by a deterministic procedure halton that generates with each evaluation a number on the unit interval (0, 1). This deter- ministic procedure should produce values that look as if random. Specifically, typical random number generators produce a stream of pseudo-random numbers, i.e. they use a source of entropy to generate new draws that are (ideally) not predictable by past draws. Another way to achieve similar results are so-called quasi-random sequences. One example is the Halton sequence. The deterministic algorithm producing Halton low-discrepancy numbers reads as follows:

• Input: Base b and Index i
• Output: A random scalar r on the interval (0, 1)
• Algorithm:
– Init: set s = 1 and r = 0
– Update: while i > 0 do
* sets = s/b
* set r = r + s(i mod b), where mod refers to the modulo operation
* set i = [i/b], where [x] indicates the largest integer less than or equal to x.
– Return r

Write a procedure halton that makes use of local state and returns with every new evaluation (halton) a new random floting point number. Copy the code we used for the Monte Carlo approximation of π and demonstrate that substituting rand with halton in the circle-test procedure yields values close to the true π.

(b) (10 points) Implement a procedure halton-stream that returns an infinite stream of Halton draws. You may reuse the procedure halton from the last subquestion or, alternatively, implement a new procedure. In case you were not able to solve the previous subquestion, use the procedure random that you find in the scheme code on lecture B1. You may also use this procedure to answer the follow-up questions.

(c) (10 points) Write a procedure make-halton-stream which allows construction of new instances of a stream of Halton numbers (similar to make-account discus- sed during the course). Implement a message passing interface and an internal procedure take that takes a single argument n. n is the number of additional draws taken from the current instance of the Halton sequence. Don’t forget to update the local state variable accordingly, such that each instance of a Halton stream memoizes its current position in the sequence.

(d) (5 points) Use the environment model of evaluation to show how (take 3) evaluates. Depict the results graphically.

(e) (5 points) Let’s say, we want to draw random numbers on an interval (1,1). How would you transform the original stream producing random numbers in the interval (0, 1) to obtain such numbers? Provide the code producing the random numbers on (1, 1).

Thank you so so much to anyone answering this before tomorrow midnight (Central European Summer Time) !!!