addition,
subtraction,
negation,
multiply and divide by powers of 2,

Now you want to add other arithmetic functions, especially multiplication and division.

We will look at 4 problems:

P_m = multiplication of two numbers (a * b)
P_d = division of two numbers (a / b)
P_r = reciprocal of a number (1 / a)
P_s = square of a number (a²)

We will be writing stuff like P₁ ≤ P₂ to mean a reduction of P₁ to P₂, similar to the book's ≤_p. However, here it's not polynomial-time, but rather an efficient reduction comparable to the other operations on these numbers. Intuitively, this means: if you can compute P₂ efficiently, then you can compute P₁ efficiently.

1. If 1000 binary bits are used for the significant part, roughly how many decimal digits of accuracy would we have? [We've seen this before: the conversion factor is log₁₀(2)=0.3010299956, so there are roughly 301 digits.]

2. Two of the reductions are trivial. Which are they? (Think about this carefully.) [P_s ≤ P_m and P_r ≤ P_d are trivial. In each case the problem on the left is a special case of problem on the right, so obviously if you can solve the problems on the right, you can solve those on the left. In each case there is a trivial reduction of the problem on the left to the one on the right: just map the problem to itself.]

3. Use the formula below to come up with another reduction: [The reduction is P_m ≤ P_s. This uses the fact that we can freely do addition, subtraction, negation and mult/div by powers of 2. The formula then clearly shows how to take squaring and use it to multiply.]
   

4. Use the formula below to come up with yet another reduction: [The reduction is P_s ≤ P_r. This is similar to the previous item. The formula on the right only involves the reciprocal (in addition to operations listed at the beginning). On the left is just a square.]
   

5. Use the following iteration formula from Newton's method (which we studied) to find another reduction.
   

   In this case you should explain in some detail how you intend to handle the initial guess for Newton's method, which should not be too far from the correct answer. [Hint: here is the page that covers this material.] [This was how we showed that if we can multiply, then Newton's method will let us calculate the reciprocal, a very big result. The reduction is P_r ≤ P_m.]

6. Argue that if you can do both P_m and P_r efficiently, then you can also do P_d efficiently.
   [This is pretty much obvious because a / b = a * (1 / b). We don't have a notation for this. Perhaps write: P_d ≤ (P_m and P_r)]

7. Argue that if we can do P_s efficiently, then we can also do the other three efficiently: P_m, P_r, and P_d. (This might be a quick and dirty way to do a half-way efficient implementation.) [Note: Not all the reductions above are needed to show this part vii.] [This follows from reductions above and transitivity:
   P_m ≤ P_s, so if we can square we can multiply,
   P_r ≤ P_m ≤ P_s so if we can square, we can find reciprocals,
   P_d ≤ (P_m and P_r) ≤ P_s and if we can square we can divide.]