# Alternative algorithms for calculating x^2?

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?

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.

• 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$). – 6005 Apr 10 '20 at 14:36
• 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. – kelalaka Apr 10 '20 at 17:47
• ... 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. – gnasher729 Apr 11 '20 at 10:03

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.

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

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