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.

| cite | improve this answer | |
$\endgroup$
  • $\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 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 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 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.

| cite | improve this answer | |
$\endgroup$
-3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 at 9:29
  • 2
    $\begingroup$ This is not a programming language specific question, I do not have access to such functions. $\endgroup$ – Faissaloo Apr 10 at 13:13
  • $\begingroup$ So you should specify that while asking question $\endgroup$ – Mohd Arsalan Apr 10 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 at 14:38
  • $\begingroup$ netlib implementation is essentially $\exp(2\log x)$. No special case for $y=2$. $\endgroup$ – Yuval Filmus Apr 21 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.