1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does this question belong on Math StackExchange instead? $\endgroup$ – ab123 Nov 9 '18 at 14:46
  • $\begingroup$ I am allowed to use them, but I do think I may have to use them. $\endgroup$ – ab123 Nov 9 '18 at 17:31
  • $\begingroup$ I asked it on MSE as well, as I wasn't getting a response here, and someone figured out the first part. You can see it here - math.stackexchange.com/questions/2991467/… $\endgroup$ – ab123 Nov 9 '18 at 17:33
  • $\begingroup$ @Klorax it uses squaring but the square can also be computed using reciprocal and sum as written in $P^2 = \frac{1}{\frac{1}{P} - \frac{1}{P+1}} - P$. Yes, I am looking for an expression involving operators. $\endgroup$ – ab123 Nov 9 '18 at 17:43
  • $\begingroup$ I cannot see whether subtraction is allowed or not. Can you list all "elementary operations"? Is division an elementary operation? Is shift or floor an elementary operation? Is remainder an elementary operation? Is maximum of two numbers an elementary operation? $\endgroup$ – Apass.Jack Nov 9 '18 at 20:02
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.