This portion of Recitation 11 is Problem 1. You are to do either PART A, or PART B below. Each part starts with an arbitrary double x and asks you to write a program which will calculate the function log₂x. For full credit, your program must not include any transcendental functions. You must include at least three runs: one inside the normalization interval, one much smaller than the lower number of this interval, and one much larger than the upper number of this interval. (The latter two runs are to test the normalization.)

The problem is similar to the work on the web page 6 Newton's Method 1. That page presents two cases: finding the square root and finding the reciprocal, both using a normalization step to transform x to x', where x' is always located in a fixed interval. Then we calculated the function of x', and completed the problem with a denormalization step to get the function applied to the original x. Both parts A and B below follow this pattern, with the normalization a multiplication (or a division) by a power of 2. In this case though, the denormalization is rather different.

Here we normalize into the interval from 1 to 2, using multiplication by powers of 2. So the interval is different but otherwise normalized exactly as we did before.

Next we need an approximation function for log₂x on the this interval:

public double approx(double x) {
   double a0 = -2.1718276908;
   double a1 =  3.0858266589;
   double a2 = -1.0780415294;
   double a3 =  0.1640425613;
   return a0 + a1*x + a2*x*x + a3*x*x*x;
}

For a picture, see graph of approximating polynomial. On the range from 1 <= x <= 2, approx(x) differs from log₂(x) by less than 0.0015.

Start with x₀ = approx(t) as an initial guess. To get the Newton approximation equation, we need the derivative of f(x) = t - 2^x. So df/dx = d/dx(t - 2^x) = d/dx(t - e^ln(2) x) = - ln(2) e^ln(2) x = - ln(2) 2^x. Starting with the guess x₀, the Newton equation for the new guess x₁ is:

After three or four iterations of Newton's method, you should have 15 digits of accuracy. Then you must denormalize, which as I said above is bit weird in this example, and is definitely different from the examples of square root or division. (Think about this carefully!).

Finally, this solution uses another transcendental function, namely 2 to a power ( pow(2,x) in Java and C ). Initially you should just use the pow function, but as a final step for Part A, you should use the power series for e^x in the form of exp(ln(2)*x) = pow(2,x). This allows us to calculate log₂t from scratch, without using any transcendental functions.

Of course the function log₂(x) that you need is just the ln(x) below divided by ln(2).

You must normalize into an interval of the form [x/2,x], where you may choose x, which can be a simple value such as 3/2, 5/4, 7/5, 13/10, and in fact any x <= 1.5 and not too close to 1 will work. I guess I recommend normalizing into [5/8,5/4] = [0.625,1.25] as a simple choice.

You must use one of these series to calculate log₂(x) for x in the interval that you choose. This part does not use an approximating function, as the applications involving Newton's method did. The series not only approximates, but calculates directly. However, these series won't work very far away from the interval that you use. That is why we have to normalize in this case also.

After using the series, you must denormalize in the same weird way that is used in Part A above. The denormalization does not depend on the particular interval that you choose, but just on the number of times you multiply (or divide) by 2 during normalization.