New answers tagged arithmetic
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
