Due Date: Wed, Mar 12, 2003
For each of the following questions, anything which your programs compute must be computed within a new method, and not directly inside your main method.
Question 1: Write a Java program which reads in a positive integer n and computes the cubed root of n. Note that you may not use Math.pow(), but rather must adapt the binary search algorithm which you used in Lab 1 to guess a number between 1 and 1 million. To accomplish this, you must “box in” your answer with a “lo” guaranteed to be no larger than the answer, and a “hi” guaranteed to be no smaller. We can start with a “lo” of 0 and a “hi” of n. Think about this! At each step, your “guess” is the average of lo and hi. If your guess is correct (that is, within some small distance of the answer), then print out the answer and exit. Otherwise, adjust hi or lo, accordingly, to be the guess and continue until you converge on the answer.
Question 2: Find pi using Monte Carlo techniques, by throwing darts randomly into the unit circle, as we discussed in class today.
Question 3: Write a Java program which reads in three positive integers, n, r, and k, and prints out the kth digit (after the decimal point) of the rth root of n. So if you read in 3, 1, 2, you should print out the 1st digit after the decimal point of the square root of 3. The answer, thus, is 7, in this case.
Question 4: [ Most of this question is borrowed from http://linus.socs.uts.edu.au/~rons/mss/Lect8.html ]: Over 5000 years ago, the ancient Babylonians discovered a method for computing the square root of 2. They probably used that number (about 1.4) to construct right angles for the foundations of their buildings. This iterative algorithm is still the simplest way to compute square roots.
If x is any number close to sqrt(2), then x2 will be close to 2, which makes x close to 2/x. But 2/x will be on the other side of sqrt(2) from x. That is, if x is less than sqrt(2), then 2/x will be greater than sqrt(2), and vice versa.
For example, suppose that x = 1.6. Then 2/x = 1.25, which is on the other side of sqrt(2). This crossing over the limit is the key to the algorithm because it means that the average of x and 2/x must be between them and therefore closer to the objective sqrt(2). So the Babylonian Algorithm consists of choosing some number x that is close to sqrt(2), and then repeatedly replacing x by its average with 2/x.
Note that, due to roundoff errors, a constant (say 0.5E-8) is necessary to ensure that the algorithm terminates after a solution of sufficient accuracy has been found.
Your task is to write a Java program which reads in a positive integer n and uses the Babylonian Algorithm to compute the square root of n, and then prints out the answer.
Question 5: Which is more efficient (that is, requires fewer steps) to compute the square root of an integer, the Babylonian Algorithm or the Binary Search Algorithm? We will address this empirically. Change your programs to not take any input. Rather, they should compute the square roots of all integers in the range [1,100,000]. Next, keep a count of every guess your algorithm makes. Print out the total number of guesses required for each algorithm, and then if these are within 10%, print out that the algorithms are roughly equivalent, otherwise print out which algorithm wins and by how much.
Question 6: The natural logarithm of 2 is written ln(2), and can be computed as follows:
= 1/1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + …
Write a Java program which uses this technique to compute the ln(2), stopping when the next term to be added or subtracted is smaller than 0.00001. Verify your answer by comparing with the value of ln(2) computed by using the builtin Java method, Math.log() (which computes the natural logarithm).
Question 7: There are two digits a and b (so a and b are both in [0,9]) such that the following is true:
(PI - a) / b = 1/(2 x 3 x 4) – 1/(4 x 5 x 6) + 1/(6 x 7 x 8) - 1/(8 x 9 x 10) + …
Write a Java program which correctly determines the values of a and b.
Hint #1: For any given a and b, keep expanding this expression until the next term is smaller than 0.000000001.
Hint #2: At that point, because
there are infinitely many terms remaining, you don’t know how far away from
the answer you remain, so be generous, and assume that this result equals the
desired answer if they are within 0.01 of each other.
See Course Home Page.