Complete each problem to the best of your ability.  The TAs and I are available and eager to help.  Be clear and thorough about your reasoning.

Problem 1: You’ve Got the Power (25 points)

Consider the problem of calculating Nk  for integer values of k > 0.  The naive way to do this is to just multiply N together k many times in a loop, for a total complexity of O(k). But we can do better.

1)  Show that if k is a power of 2, i.e., k = 2m  for some m, then you can compute Nk  via repeated squaring in O(m) multiplications.

2)  Argue then that for any k, you can compute all the powers N 1 , N2 , N4 , N8 , ..., i.e., all N2i   < Nk  in O(log2 k) multiplications.

3)  True or false: you can also compute all these powers in O(ln k) multiplications. Why or why not?

4)  Note that with the powers of N to powers of 2, you can compute other powers as well - note for instance that N7  = N 1 * N2 * N4 .  Show that for any k, given the powers of N to powers of 2 you need, you can compute Nk  in O(ln k) multiplications. Hint:  What are the largest powers of N to the powers of 2 you might need?

5)  To summarize: show that you can do all of this (compute the powers of N to the powers of 2 and multiply the necessary ones together) and compute Nk  in at most O(ln k) multiplications.  How does this compare to the naive approach?

Problem 2:  Significant Factors (25 Points)

For a given integer N , a problem of frequent interest is determining a) if N is prime, and b) if N isn’t prime, what are the factors of N , i.e., find a, b such that N = a * b. This is generally a hard problem.

1)  Show that if N has factors, one of those factors is less than or equal to ^N .

2)  Argue then that testing numbers as factors via trial division, factoring N is O(^N) many operations.  Hint: What are the worst cases you need to  consider?

3)  Frequently the complexity of numerical calculations is expressed as a function of the number of digits of N . The more digits, the harder the calculation becomes. Show that the number of digits of N is O(ln N).

4)  Argue that factoring via trial division is exponential in the number of digits of N .

5)  Do some research on the best factoring algorithm you can find. What is its complexity, in terms of ln N? How does it compare?

Some numbers are easy to factor, however.  Suppose you wanted to test whether or not N is a perfect power, i.e., N = ak  for some integer base a and power k .

6) What are the smallest a and largest k you may need to consider?

7) What are the largest a and smallest k you may need to consider?

Consider the following algorithm to test whether or not N is a perfect square.  Note that if N is a perfect square, its square root must lie in the interval 1, 2, 3, . . . , N . We can do a binary search in the following way: starting with a test value of a in this interval, we can compute a2 . If this is too large, compared to N , we look at the smaller half of the interval and pick a new a in the middle. If this is too small compared to N , we look at the larger half of the interval and pick a new a in the middle. This is iterated until either we fine a such that N = a2 , or we show that no such a can exist.

8)  Argue that this requires testing O(ln N) many a values.  With one multiplication per a value, show that this search can be done with complexity O(ln N).

We can generalize this to test N as a perfect power for any power k .

9)  Show that N can be tested as a perfect k power in at most O(ln N) many tests.

10)  Using the result of the first problem in this assignment, show that a test for N as a power k can be done in complexity O((ln N) * (ln k)).

The above two questions consider a specific k value. If we consider checking every necessary k value,

11) What is the overall complexity in terms of N? Give the tightest big O you can.

12)  How does this complexity compare to naive factoring?  How does it compare to the best possible factoring algorithm?

Problem 3: The Root of It (25 Points)

We can mimic the square root of algorithm of the previous problem to compute real valued square roots as well. This is known as the bisection method. We can apply that here in the following way:

● Take the initial interval [a0 , b0] = [1, 2]. Let x0  = 1.5, the midpoint of this interval.

● At any step n > 0, with interval [an , bn] and midpoint xn ,

– If xn(2)  > 2, take the smaller half of the interval:  [an+1, bn+1] = [an , xn] and xn+1  = (1/2)(an + xn ).

– If xn(2)  < 2, take the larger half of the interval:  [an+1, bn+1] = [xn , bn] and xn+1  = (1/2)(xn + bn ).

1)  Argue that ^2 always lies between an  and bn  for all n.

2)  Argue that |bn - an | < (1/2)n .

3)  Argue therefore that xn converges to ^2 as n 二 o, and the error on xn  (how much it differs from^2) decreases like O((1/2)n ).

Here’s an alternative algorithm to calculate the square root of 2.

● Define y0  = 1.5

● At any step n > 0, define

yn+1  =  ╱yn + 、 .

(1)