Algorithms for elementary operations using other elementary operators

146 Views Asked by At

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.

1

There are 1 best solutions below

0
On

How about writing $AB = \frac{1}{2}((A+B)^2 - A^2 - B^2)$ and using the $P^2 = \frac{1}{\frac{1}{P} - \frac{1}{P+1}} - P$.