1
$\begingroup$

I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?

$\endgroup$
4
$\begingroup$

Base on the fact that:

If n is an even number $(n = 2m) \implies n^2 = 4m^2$

If n is an odd number $(n = 2m + 1) \implies 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 complexity.

$\endgroup$
3
  • $\begingroup$ Nice approach, +1. I haven't thought about this before. I guess there are some optimizations (skipping the recursion once the bitwise shift causes the number to become $0$). $\endgroup$ – 6005 Apr 10 '20 at 14:36
  • 1
    $\begingroup$ This needs more performance analysis like the number of additions. The transformation is fine as longs as the cost of additions is not higher the replaced multiplications as in Karatsuba. $\endgroup$ – kelalaka Apr 10 '20 at 17:47
  • $\begingroup$ ... where n is the number of bits in the number. For products of huge numbers you could do something similar increasing the number size by say 64 bit at a time. May be a little bit more efficient than generic multiplication. $\endgroup$ – gnasher729 Apr 11 '20 at 10:03
0
$\begingroup$

You can use $x^2 = \exp(2\log x)$.

However, this is probably inferior to using $x^2 = x \cdot x$ in almost all situations.

$\endgroup$
-3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Obviously if that function is implemented in any not completely brain-damaged way, then it will calculate pow(x, 2) as x*x. $\endgroup$ – gnasher729 Apr 10 '20 at 9:29
  • 2
    $\begingroup$ This is not a programming language specific question, I do not have access to such functions. $\endgroup$ – 0x777C Apr 10 '20 at 13:13
  • $\begingroup$ So you should specify that while asking question $\endgroup$ – Mohd Arsalan Apr 10 '20 at 13:15
  • 3
    $\begingroup$ This site is for general computer science (conceptual) questions; so specifying that it is not language-specific is not necessary. $\endgroup$ – 6005 Apr 10 '20 at 14:38
  • $\begingroup$ netlib implementation is essentially $\exp(2\log x)$. No special case for $y=2$. $\endgroup$ – Yuval Filmus Apr 21 '20 at 9:37

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.