# Tag Info

0

You can simply use pow(x,2) this comes under the library #include<math.h>

0

Base on the fact that: If n is an even number ($n = 2m$) => $n^2 = 4m^2$ If n is an odd number ($n = 2m + 1$) => $n^2 = 4m^2 + 4m + 1$ And you can calculate $m$ by bitwise shifting right of $n$, calculate $4m$ (or $4m^2$) by bitwise shifting left. So you can apply the recursion method to this process to establish the result with $O(log(n))$ time ...

2

Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.

Top 50 recent answers are included