Algorithms for elementary operations using other elementary operators

Question

The question asks to provide an algorithm to compute

$(i)$ The product of $n$-bit numbers using reciprocation operation and addition operation but not using multiplication and squaring.

$(ii)$ The square of a polynomial of degree $n−1$ using only reciprocation and addition operation but not using multiplication and squaring.

$(iii)$ The product of two $n − 1$ degree polynomials using only squaring and addition operations but not using multiplication and reciprocation operations

All the operations stated above are on $n$-bit integers.

My try: The question asks to express some operator in terms of other elementary operators , so for eg. for (i) I tried writing $(\frac{1}{A} + \frac{1}{B})^{-1} = \frac{AB}{A+B}$, but to get $AB$, I still have to multiply LHS by $A + B$. I think I can do $(ii)$ if I do $(i)$ as a polynomial is similar to a n-bit integer if you consider the bits as $(a_ix^i)$. I don't have an idea for $(iii)$ yet.

Answer 1

Throughout this answer, when we say we will be using some operations, it implies that no other operations is allowed. We also assume 1 is available as an operand.

The above clarification is considered as an improvement of original statement of problems. There will be further modification/clarification of the original problems, which have to be made because of the ambiguity of the original problems.

---

Here is the answer to part (i)

Part (i). The product of two non-zero numbers using only reciprocation operation and subtraction operation.

Please note I have replaced by addition by subtraction; otherwise, it is impossible. Also I removed the specification of $n$-bits, which seems distracting and harmful; otherwise, $\dfrac13$ is problematic. I have also added the condition that the numbers are non-zero. Otherwise, we have to add an operation that checks whether a number is non-zero and acts accordingly. Also 1 have to be available. Otherwise, we cannot produce 1, which is needed in the final operation.

Let the two non-zero numbers are $A, B$.

1. we get addition by $X+Y=X-((Y-Y)-Y)$.
2. we get 4=1+1+1+1.
3. we get $X\to \dfrac {X^2}4$ by $\dfrac {X^2}4=X+\dfrac1{\dfrac1{X-4}-\dfrac1X}$.
4. We get multiplication by $AB=\dfrac{(A+B)^2}4-\dfrac{(A-B)^2}4$.

This answer at mathoverflow uses division by 2 or multiplication by $\dfrac12$ without explanation, which can be considered as a minor flaw. In fact, we can do division by 2 as $\dfrac A2=\dfrac1{\dfrac1A+\dfrac1A}$.

---

Part (ii). The square of a polynomial with given coefficients using only reciprocation and subtract operation.

Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, this part can be done easily as a consequence of part (i).

---

Part (iii). The product of polynomials with given coefficients using only squaring and subtraction operations and division by 2.

We get addition by $X+Y=X-((Y-Y)-Y)$. We get multiplication by $XY=\dfrac{(X+Y)^2-X^2-Y^2}2$. Since the coefficient of the square of a polynomial is the sum of products of various coefficients of that polynomial, we can compute the product of two polynomials.

Note that division by 2 is needed. Otherwise, it can be proven that it is not possible to do multiplication although we have $2XY=(X+Y)^2-X^2-Y^2$.